[BOJ 2309] 일곱 난쟁이

이 문제는 전체 탐색으로 문제를 해결할 수 있다.

 

 

 

주의해야 할 점은, 100을 만드는 7명의 난쟁이를 찾아야 한다는 것이다.

 

 

 

벡터를 이용해서, 출력문을 손쉽게 해결했다.

 

 

 

해설코드(C++).

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int tall[10];
vector<int> v;
bool flag = true;
 
void func(int idx, int sum){
    if(idx == 10){
        if(sum == 100 && v.size() == 7){
            if(flag){
                vector<int> tmp;
                for(int i = 0; i < v.size(); i++)
                    tmp.push_back(tall[v[i]]);
                
                sort(tmp.begin(), tmp.end());
                for(int i = 0; i < tmp.size(); i++)
                    cout << tmp[i] << endl;
                
                flag = false;
            }
        }
        return;
    }
    
    if(sum + tall[idx] <= 100){
        v.push_back(idx);
        func(idx + 1, sum + tall[idx]);
        v.erase(v.end() - 1);
    }
    
    func(idx + 1, sum);
}
 
int main() {
    for(int i = 1; i <= 9; i++)
        cin >> tall[i];
    
    func(1, 0);    
    
    return 0;
}