[백준 2309번] 일곱 난쟁이

문제 링크

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

알고리즘

문제가 되게 짧고 간결하다. 그래서 쉬운 문제인데 나는 왜이렇게 오래 걸렸을까..

먼저, 단순히 생각해보면 그냥 조합 문제다. 9C7 = 9C2 = 36. 경우의 수를 따져봐도 36가지밖에 되지 않는 조합 문제.

그리고 조건에 해결되지 않은 경우는 없고, 답이 여러 개인 경우 한 가지만 출력하면 된다고 하니 얼마나 깔끔한 문제인가.

그래서 그냥 조합 코드를 짜고, 답을 어떻게 출력할 것인가만 고민하면 된다.

나는 좀 무식하게 더할때마다 값을 배열에 넣고, 만약 합이 100이 되는 순간에 변 수 하나를 조작해줘서 더 이상 값을 배열에 넣지 않도록 만들어 주게 만들었다.

합이 100이 되는 순간 함수 구동이 끝나고 출력이 되면 좋을텐데, 거기까지는 생각을 못해보겠다. 아마 그 경우는 함수를 하나 더 쓰거나 재귀를 안쓰지않을까?

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
int isvisited[9] = {0,};
int sum = 0;
int height[9];
int answer[7];
int indexx = 0;
int clear = 0;
void calc(int n, int cnt){

    if(sum == 100 && cnt == 7){
        clear = 1;
        return;
    }

    if(cnt > 7 || sum > 100) {
        return;
    }

    for (int i = n; i<9; i++){
        if(isvisited[i] == 1)
            continue;

        if(clear == 0) {
            sum += height[i];
            answer[indexx] = height[i];
            ++indexx;
            isvisited[i] = 1;

            calc(i, cnt + 1);

            sum -= height[i];
            --indexx;
            isvisited[i] = 0;
        }
    }
}

int main(){
    for (int i = 0; i<9;i++)
        cin >> height[i];
    calc(0,0);
    sort(answer, answer+7);
    for (int i = 0; i<7; i++)
        cout << answer[i] << '\n';
}