백준[브루트포스] 일곱난쟁이 문제

일곱난쟁이인줄 알았던 백설공주는 알고보니 난쟁이가 9명이었다고 한다.

 

그래서 백설공주는 일곱난쟁이의 키가 합이 100이 되는걸 알게되어서 누가 진짜 난쟁이인지 알고싶다고 한다.

 

이 문제는 백준 2309번을 보면 풀 수 있고 저는 순열을 이용해서 풀었습니다.

 

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

2309번: 일곱 난쟁이

 

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

int main(){
    int n = 9;
    vector<int> a(n);
    vector<int> b(n);
    for(int i=0; i<9; i++){
        cin>>a[i];
    }
    for(int i=0; i<7; i++){
        b[i] = 1;
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    do {
        int sum=0;
        for(int j=0; j<9; j++){
            if(b[j]==1){
                sum+=a[j];
            }
        }
        if(sum==100) break;
        
    } while (next_permutation(b.begin(), b.end()));
    vector<int> ans(7);
    int x =0;
    for(int i=0; i<n; i++){
        if(b[i] == 1){
            ans[x] = a[i];
            x++;
        }
    }
    sort(ans.begin(), ans.end());
    for(int i=0; i<7; i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}