[백준] 18429번 근손실 C++

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

C++

#include<iostream>
#include<algorithm>
using namespace std;

bool visited[9];
int n,k,total = 0;
int arr[9];

void search(int num, int weight) {
    if(weight < 500) {
        return;
    }
    if(num == n) {
        total++;
        return;
    }
    for(int i = 0; i < n; i++) {
        if(!visited[i]) {
            visited[i] = true;
            search(num+1, weight + arr[i] - k);
            visited[i] = false;
        }
    }
}


int main() {
    // 항상 500이상
    // 3! 조합 함수
    // next_permutation 함수,,,,, 중복 원소가 있으면 중복 제거된 순열만 생성한다....
    // 마구 난사하면 안된다라는 교훈,,,
    // 그럼 뭐 직접 만들어야지 휴
    // 그림 그려보는게 진짜 중요하다!
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

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

    search(0,500);
    cout << total << "\n";
}

문제풀이

• STL을 사용해서 풀어봤지만 오답이라고 나와서 한창동안 고민했던 것 같다. 그 결과 중복이 있을 경우 무시된다는 사실을 깨닫게 되었고 직접 함수를 구현했다. 먼저 총 n개의 키트를 의미하는 num과 항상 줄어드는 weight를 매겨변수로 가지는 함수를 만들었다. 그리고 weight < 500이면 무조건 탈락이고 모두 돌아가을 경우 total++해줬다. 그리고 처음으로 bool 함수 visited를 사용해봤다. 아직 방문하지 않은 키트라면 방문했다고 표시한 다음(true) 재귀함수를 돌린다. 계속해서 재귀를 돌렸을 때 잘 돌아가면 total++이고 아닌 경우는 다시 visited를 방문하지 않은 상태로 변경한다.

Comment

• next_permutation은 중복이 있을 경우 무시한다!!!! 이 문제는 경우의 수 합을 구하는 문제인데 조건에 부합한 경우도 무시될 수 있다. STL 난사하면 안된다...