[BOJ] - 2309. 일곱 난쟁이

[URL]

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

[풀이 과정]

1. 난쟁이 9개 오름차순 정렬

2. 9개 중 2개 선택 (재귀 활용 완전 탐색)

3. 9개의 합에서 2개의 합을 빼서 100이면 정답

4. 7개 난쟁이 정답 오름차순으로 출력

 

[소스 코드]

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int arr[9];                    // 난쟁이 9명 
bool check[9] = { 0, };        // 9명 중 2명 체크
int cand[2];                // 제외 시킬 2명 index 저장
int sum9 = 0;                // 9명의 합
int dap[2];
 
void go(int cnt)
{
    if (cnt == 2)
    {
        if (sum9 - (arr[cand[0]] + arr[cand[1]]) == 100) {        // (전체 9명 합 - 제외 시킬 2개 합) == 100 이면 당첨
            dap[0] = cand[0];
            dap[1] = cand[1];
        }
        return;
    }
 
    for (int i = cand[cnt - 1]; i < 9; i++)
    {
        if (check[i] == false)
        {
            check[i] = true;
            cand[cnt] = i;
            cnt++;
 
            go(cnt);
 
            cnt--;
            check[i] = false;
        }
    }
}
 
int main() {
 
    for (int i = 0; i < 9; i++)
    {
        scanf("%d", &arr[i]);
        sum9 += arr[i];
    }
 
    sort(arr, arr + 9);        //오름차순 정렬, 출력을 위해서~
    go(0);
 
    for (int i = 0; i < 9; i++)
    {
        if (i == dap[0] || i == dap[1])
        {
            continue;
        }
        printf("%d\n", arr[i]);
    }
 
    return 0;
}