[백준] 2309번 : 일곱 난쟁이 - [C++]

링크: [백준] 2309번 : 일곱 난쟁이

문제

설명

어제 오늘부터, N과 M 시리즈를 풀면서, 재귀 함수를 이용한 백트래킹 알고리즘을 열심히 연습했고, 해당 문제가 완전 탐색 유형이기 때문에 백트래킹 알고리즘을 활용해서 문제를 풀어봤습니다.
다른 분들 풀이를 보니까, 다른 분들은 for문을 3번 써서 재귀 함수를 쓰지 않고 문제를 해결했습니다.

제 생각에는 재귀 함수를 쓰면 좀 더 일반적인 상황에서의 풀이가 될 것 같아서 공유하게 됐습니다.

저의 재귀 함수 풀이와 저의 for문 풀이를 함께 올리도록 하겠습니다.

평소에 그냥 문제 풀고 포스팅은 따로 안 했는데, 이번 문제는 풀이도 다양하고, exit()를 처음 접해서 올리게 됐습니다.

특이한 부분에 대한 주석도 포함했습니다!

풀이

재귀함수를 이용한 풀이 (주석을 자세히 썼습니다...)

아래 사진이 코드의 DFS 트리를 그려본 것입니다!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm> #sort알고리즘을 사용하기 위함.
using namespace std;
int cnt = 0, sum = 0, arr[10], ch[10];

void DFS(int L) { #L은 DFS 트리의 레벨(혹은 깊이)를 의미합니다.
    if (cnt == 7) {
        if (sum == 100) {
        #cnt(count의 약자)가 7일 때, 합이 100인 경우가 출력을 해야하는 경우입니다.
            for (int i = 1;i <= 9;i++)
                if (ch[i] == 1)
                    cout << arr[i] << "\n";
            exit(0); #주의할 부분입니다.
//문제에서 '가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.'라고 했고, 
//'일곱 난쟁이를 찾을 수 없는 경우는 없다.'라고 했기 때문에
//합이 100인 경우가 무조건 존재하고,
//여러 경우 중에 처음 등장하는 경우 한번만 출력하면 되기 때문에
//#exit(0)를 이용해서 재귀함수를 완전히 빠져나와야합니다.
//달리 이야기하면, return으로 빠져나오는 것이 아니라,
//stack에 남아있는 모든 함수를 종료해야 합니다.
//그래서 제 풀이의 경우, exit(0)를 이용해서 빠져나와야 문제가 해결됩니다.
        }
        return;
    }
    if (L == 10)
    //DFS의 깊이가(L) 9를 넘어서는 경우, return해서 마무리해야 DFS가 무한히 반복되지 않습니다.
        return;
    else {
        sum += arr[L];
        ch[L] = 1;
        cnt++;
        DFS(L + 1);
        
        //ch[L](check의 약자로, 값을 받아서 더했는지 안 더했는지를 0, 1로 구분합니다.
        //sum에 계속 더해주고
        //sum에 더해줄 때마다 cnt++을 해서 확인한 '난쟁이 키'가 몇 개인지 저장합니다.
        
        sum -= arr[L];
        ch[L] = 0;
        cnt--;
        DFS(L + 1);
        //키를 더하지 않을 때의 경우입니다.
    }
}

int main(int argc, const char* argv[]) {
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    for (int i = 1;i <= 9;i++)
        cin >> arr[i];
    sort(arr + 1, arr + 10);
    DFS(1);
    return 0;
}

for문을 3번 쓴 풀이

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

int main(int argc, const char* argv[]) {
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    int a[10], sum = 0, i, j, k;

    for (i = 1; i <= 9; i++) {
        cin >> a[i];
        sum += a[i];
    }
    sort(a + 1, a + 10);
    for (i = 1; i <= 9; i++) {
        for (j = i+1; j <= 9; j++) {
            if (sum - a[i] - a[j] == 100) {
                for (k = 1; k <= 9; k++) {
                    if (k != i && k != j) {
                        cout << a[k] << "\n";
                    }
                }
                return 0;
                //단 한번의 경우만 출력하면 되기 때문에, 최초로 등장한 경우만 출력하면 됩니다.
            }
        }
    }
    return 0;
}