[백준 2309] 일곱 난쟁이

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

2309번: 일곱 난쟁이

백준 2309 일곱 난쟁이입니다.

최근 코테 예정이 없어서 느슨했지만 그래도 풀기위해 간단히 풀어본 문제입니다.

 

풀이입니다.

단수히 9명의 난쟁이 중 7 난쟁이를 골라서 합이 100인지를 dfs를 돌면서 브루트포스로 확인하면 되는 문제입니다.

 

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
vector<int> v;
int visit[9],arr[9];
void dfs(int idx, int cnt, int sum) {
    if(cnt == 7) {
        if(sum == 100){
            sort(v.begin(), v.end());
            for(int i=0;i<v.size();i++) cout << v[i] << ' ';
            exit(0);
        }
        return;
    }

    for(int i = idx+1; i<9;i++) {
        if(i>=9 || visit[i]) continue;
        visit[i] = 1;
        v.push_back(arr[i]);
        dfs(i, cnt+1, sum+arr[i]);
        visit[i] = 0;
        v.pop_back();
    }

}
int main() {

    for(int i=0;i<9;i++) cin >> arr[i];
    for(int i=0;i<3;i++) {
        visit[i] = 1;
        v.push_back(arr[i]);
        dfs(i, 1, arr[i]);
        visit[i] = 0;
        v.pop_back();
    }
}