[백준 2309] 일곱 난쟁이, c++

www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

진짜 일곱 난쟁이를 찾는 문제 총 9명중 7명을 고르는 문제다. 문제의 조건 중 일곱 난쟁이의 키의 합이 100이라고 한다. 따라서 7명을 고르는 모든 경우의 수를 확인하면서 7명의 합이 100일 때 오름차순으로 출력하고 종료를 하면 된다.

문제 해결을 위해 next_permutation()을 이용하였다. { 0, 0, 1, 1, 1, 1, 1, 1, 1 }으로 만들 수 있는 모든 경우의 수를 만들고 1일 때 해당 위치의 값을 더하여 문제를 해결하였다.

#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main() {
    int t = 9;
    vector<int> v, u;
    while (t--) {
        int tmp;
        scanf("%d", &tmp);
        v.push_back(tmp);
    }
    for (int i = 0; i < 2; i++) {
        u.push_back(0);
    }
    for (int i = 0; i < 7; i++) {
        u.push_back(1);
    }
    
    do {
        int total = 0;
        vector<int> result;
        for (int i = 0; i < u.size(); i++) {
            if (u[i] == 1) {
                total += v[i];
                result.push_back(v[i]);
            }
        }
        if (total == 100) {
            sort(result.begin(), result.end());
            for (int i = 0; i < result.size(); i++) {
                printf("%d\n", result[i]);
            }
            return 0;
        }
    }while (next_permutation(u.begin(), u.end()));
}