C++ 백준 2309 일곱난쟁이

처음 문제를 보고 완전탐색을 하면 되겠다고 생각하였지만 어떻게 구현할지 바로 떠오르지 않았습니다.
조금 시간이 걸렸던 문제라 공부할겸 기록하게 되었습니다.

처음 시도 한 풀이로 재귀를 이용하여 풀었습니다.

#include <bits/stdc++.h>
using namespace std;
int tall[10];
bool vis[10];
int tot;

void solve(int idx, int k) {
    if(k == 7) {
        if(tot == 100) {
            for(int i=0; i<9; i++) {
                if(vis[i]) {
                    cout << tall[i] << '\n';
                }
            }
            exit(0);
        }
        return;
    }

    for(int i=idx; i<9; i++) {
        if(!vis[i]) {
            vis[i] = true;
            tot += tall[i];
            solve(idx+1, k + 1);
            vis[i] = false;
            tot -= tall[i];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for(int i=0; i<9; i++)
        cin >> tall[i];
    sort(tall, tall+9);
    solve(0, 0);
}

각 재귀호출마다 한 명의 난쟁이를 결정하고, 7명이 되면 키의 합이 100이 되는지 확인합니다. 100이 되는 경우 중 제일 먼저 나온 케이스를 출력하고 종료하도록 코드를 작성하였습니다.

두번 째 풀이로 반복문을 이용하여 풀었습니다.

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

int num[9], result[7];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int total;
    for(int i=0; i<9; i++)  cin >> num[i];

    // 9명중 2명 뺀 모든 조합 고려
    for(int a=0; a<8; a++) { // 처음부터 8번째까지의 난쟁이 고려
        for(int b=a+1; b<9; b++) { // a+1부터 9번째까지의 난쟁이 고려 
            total = 0; // 매 실행마다 total 초기화
            for(int c=0, i=0; c<9; c++) { // 처음부터 끝까지 확인
                if (c != a && c != b) { // 만약 a와 b 난쟁이가 아니면
                    result[i++] = num[c]; // 결과에 추가
                }
            }
            for(int i=0; i<7; i++) total += result[i]; // 결과의 합이 100인지 확인
            if (total == 100) // 결과가 맞으면
                break;
        }
        if(total == 100) // 결과가 맞으면
            break;
    }

    sort(result, result+7); // 정렬
    for(int i=0; i<7; i++)
        cout << result[i] << '\n';

}

// 시간 복잡도 n^3 

다시 보니까 어렵게 푼 것 같아서 조금 더 직관적으로 풀이를 해보았습니다.

#include <bits/stdc++.h>
using namespace std;
int tall[10];
int tot;


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for(int i=0; i<9; i++)
        cin >> tall[i];
    sort(tall, tall+9); // 정답을 오름차순으로 출력하므로 정렬
    tot = accumulate(tall, tall+9, 0); // 전체 9명의 키 합을 구함

    for(int i=0; i<8; i++) { 
        for(int j=i+1; j<9; j++) { // 모든 난쟁이들 탐색
            if(tot - (tall[i] + tall[j]) == 100) { // 만약 전체에서 두 난쟁이를 뺀 값이 0이 되면 조건 만족
                for(int k=0; k<9; k++) { 
                    if(k != i && k!= j) { // i와 j를 제외한 모든 난쟁이 출력
                        cout << tall[k] << '\n';
                    }
                }
                return 0; // 출력 후 종료
            }
        }
    }
}

쉬운 브루트포스 문제가 금방 풀리지 않는 것을 보아 아직 기초가 부족한 것 같다...