[백준(BOJ)] 18429번 근손실 C++

문제 : https://www.acmicpc.net/problem/18429

18429번: 근손실

 

 

어떤 문제인가?

ㅋㅋㅋ참 웃긴 문제이다.

간단하게 문제를 설명하자면 하루에 운동을 마쳤을 때 중량이 500 이하로 되지 않게 하는 루틴을 짜면 된다.

정확히 루틴을 짜는 것이 아니라 가능한 경우의 수를 구하면 된다.

 

 

 

접근 방법

일단 가능한지 불가능한지를 확인하긴 위해선 루틴의 순서가 필요하다.

이 경우에는 순열을 사용해야 한다.

 

경우의 수를 모두 측정하기 위해선 모든 루틴을 탐색(완전 탐색)을 해야 한다.

 

int n, k;
cin >> n >> k;
int arr[n + 1];

for (int i = 0; i < n; i++) {
    cin >> arr[i + 1];
}

간단하다. 문제에서 요구하는 변수들을 입력받고 배열에 중량 증가량을 저장한다.

 

vector<int> kit;

for (int i = 1; i <= n; i++) {
    kit.push_back(i);
}

 

kit라는 벡터에 1부터 n까지 저장한다.

따라서 벡터에는 운동 키트 번호

배열에는 중량 증가량이 저장되어있다.

 

 

int cnt = 0;

 

경우의 수를 카운트할 cnt변수를 선언해준다.

 

 

do {
    int total = 500;
    for (auto iter = kit.begin(); iter != kit.end(); iter++) {
        total += arr[*iter];
        total -= k;
        if(total < 500){
            break;
        }
    }
    if (total >= 500) {
        cnt++;
    }
} while (next_permutation(kit.begin(), kit.end()));

 

이제 next_permutation함수를 통해 순열을 구할 것이다.

실행문에 for문을 통해 순열이 된 벡터를 탐색한다.

탐색하며 500에 운동 증가량을 더하고 중량 감소량을 빼준다.

즉 for문 한 번이 하루인 것이다.

이때 중량이 500 이하가 된다면 break를 통해 탈출하고 다음 순열로 넘어간다.

당연히 경우의 수는 증가하지 않는다.

 

cout << cnt;

이렇게 모든 순열을 탐색한 다음경우의 수를 출력해주면 끝이다.

 

 

무엇이 어려웠는가?

문제를 읽고 순열을 사용해야겠다는 것을 파악하고 next_permutation함수를 알았다면 

큰 어려움 없이 풀 수 있었던 문제인 것 같다.

문제에서 요구하는 구현 자체가 어렵진 않았다.

 

 

배운 점

문제를 읽고 순열을 사용해야 함을 알았지만 이를 어떻게 구현해야 할지는 잘 몰랐다.

선배님께서 가르쳐주신 next_permutation함수를 생각해 문제를 해결할 수 있었다.

stl에 내장되어있는 다양한 함수들을 더 많이 알고 싶다는 생각을 했다.

또, next_permutaion함수를 사용하지 않고 순열을 구현해보고 싶다.