[Softeer] 택배 마스터 광우(Lv.3) - Day5

📋 개요 

Day5에는 GINI야 도와줘를 풀이해보았다. BFS로 경로를 찾는 것이였다.

2024.01.30 - [Algorithm/Problem] - [Softeer] GINI야 도와줘(Lv.3) - Day5

[Softeer] GINI야 도와줘(Lv.3) - Day5

이번에 풀어볼 문제는 택배 마스터 광우이다. 그리디인줄 알았는데 우선 대입해서 하는 브루트 포스와 순열로 풀어야한다.

https://softeer.ai/practice/6273

Softeer - 현대자동차그룹 SW인재확보플랫폼

---

🧩 문제

여름 휴가를 떠나기 위해 용돈이 필요했던 광우는 H택배 상하차 아르바이트를 지원 했다. 광우는 평소에 운동을 하지않아 힘쓰는 데에 자신이 없었지만, 머리 하나 만큼은 비상해 택배가 내려오는 레일의 순서를 조작해서 최소한의 무게만 들 수 있게 일을 하려고 한다.

레일은 N개이며, 각각의 레일은 Ni 무게 전용 레일로 주어진다. (같은 무게의 레일은 주어지지 않는다.) 레일의 순서가 정해지면 택배 바구니 무게(M)를 넘어가기 전까지 택배 바구니에 택배를 담아 들고 옮겨야 한다. 레일 순서대로 택배를 담되, 바구니 무게를 초과하지 않은 만큼 담아서 이동하게 되면 1번 일한 것으로 쳐준다. (단, 택배는 순서대로 담아야 하므로 레일의 순서를 건너 뛰어 담을 수는 없다)

총 K번 일을 하는데 최소한의 무게로 일을 할 수 있게 광우를 도와주는 프로그램을 만들어 보자.

⛔ 제약조건

3 ≤ N ≤ 10

max(Ni) < M ≤ 50

1 ≤ K ≤ 50

1 ≤ Ni ≤ 50

📝  형식 

📥 입력	📤 출력
첫째 줄에는 레일의 개수 N, 택배 바구니의 무게 M, 일의 시행 횟수 K가 주어진다. 그 다음 줄에는 Ni개의 택배 레일의 전용 무게가 주어진다. (택배 바구니는 무조건 택배보다 작은 경우는 없다.)	출력으로는 광우가 일 해야하는 최소한의 택배 무게를 출력한다.

💡  예제

🔢 번호	📥 입력	📤 출력
1	50 20 4 5 8 10 19 7	54
2	9 25 50 1 21 2 22 3 23 4 24 10	772

🖥️ 내 코드

---

📖  해설 및 느낀점

# C++ 문법  - next_permutaion

이 문제에서는 순열을 사용해야한다. 순열이 어떤거냐면, 우리가 흔히 수학책에 자주 나오는 주머니에서 색깔공을 순서대로 꺼내는 것으로 생각하면 된다. 주머니에서 색깔 공이 4개 있다고 생각하면 순열은 어떻게 될까?

 

{0 1 2 3} {0 1 3 2} {0 2 1 3} {0 2 3 1} {0 3 1 2} {0 3 2 1} {1 0 2 3} {1 0 3 2} {1 2 0 3} {1 2 3 0} {1 3 0 2} {1 3 2 0} {2 0 1 3} {2 0 3 1} {2 1 0 3} {2 1 3 0} {2 3 0 1} {2 3 1 0} {3 0 1 2} {3 0 2 1} {3 1 0 2} {3 1 2 0} {3 2 0 1} {3 2 1 0}

 

이렇게 나온다. 그렇다면 C++에서 이걸 어떤 방식으로 구현을 할 수 있을까? 신기하게도 C++ permution(순열)을 할 수 있는 함수가 있었다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> elements = {0, 1, 2, 3}; // 4개의 요소를 가진 벡터
    int count = 0; // 순열의 개수를 세기 위한 카운터

    do {
        // 순열 출력 (선택적)
        for (int element : elements) {
            cout << element << " ";
        }
        cout << "\n";

        count++; // 순열 개수 카운트
    } while (next_permutation(elements.begin(), elements.end()));

    cout << "순열 갯수: " << count << "\n";

    return 0;
}

 

next_permutaion을 사용하려면 오름차순으로 정렬되어있어야한다. 아래 풀이에서도 오름차순으로 정렬은 진행한 후에 함수를 활용해서 순열을 찾아내는 것을 볼 수 있다.

 

물론, 내림차순으로 정렬되어있을때도 prev_permutation을 활용해서 순열을 뽑아낼 수 있다.

https://cplusplus.com/reference/algorithm/next_permutation/

https://cplusplus.com/reference/algorithm/next_permutation/

#코테 유형 - 브루트 포스

브루투 포스는 정보보안에서 나온 알고리즘이다. 알고리즘..?이라고 해야하나? 그냥 무식하게 모든 값을 다 넣는 것이다. 그냥 직역을 하면 "무차별 검색"이라는 말이 가장 잘 어울릴거 같다.

 

Brute(짐승 같은, 난폭함) Force(힘) 걍 무식하게 다 때려 넣는 방식이다. 코테 유형 중에도 자주 나오는 문제이다. 하지만 항상 접근할때 이렇게 무식하게 한다고? 라는 생각이 들지만 대게 이런 경우 브루트 포스로 풀리는 경우가 많다.

 

그래서 내 개인적인 팁은 일단 브루트 포스로 짜보는 것을 추천한다. 괜히 짱구 굴리다가 시간이 다 지나갈 수도 있다고 생각한다.(이건 알고리즘을 이제 입문한 나의 개인적인 생각이다.)

https://namu.wiki/w/%EB%B8%8C%EB%A3%A8%ED%8A%B8%20%ED%8F%AC%EC%8A%A4

브루트 포스 - 나무위키

# 문제 풀이

이번에도 마찬가지로 문제를 읽고 내가 해야하는 코딩해야할 것들을 정리해야한다.

1. 입력
2. 작업 정렬 ➡️ next_permutation을 위해서
3. 순열 생성 및 탐색 ➡️ next_permutation 활용, 무차별 대입  
4. 작업량 계산
5. 출력

자바에서는 최대 값을 Integer.MAX_VALUE로 표현하는데 C++에서는 따로 표현할 수 있는 방법이 없어 9e8로 표현을 했다. int내에서 최대로 가깝게 표현을 해두었다. 사실 작성하면서 max로 표현하는 방법이 있어서 공유한다.

#include <iostream>
#include <limits>

int main() {
    std::cout << std::numeric_limits<int>::max() << std::endl;
    return 0;
}

 

이번 회차부터는 문제의 난이도가 급 상승한거 같다..... 매우 어려웠고 문제를 푸는 시간도 많이 걸려서 서칭을 하면서 이곳저곳에서 힌트를 얻어서 진행했다.

 

잘짠 C++ 코드가 아닐지라도 피드백 남겨주시면 감사하겠습니다!