2309

 

백준의 2309 문제를 읽었을 때  조합이 생각났다. 

 

9명 중 7명을 뽑아 키의 합이 100인 경우 통과이며, 가능한 정답이 여러 개인 경우가 있다고 했기 때문에 정답 시 프로그램을 종료 시켜야한다.

 

이를 기반으로 코드를 작성해보자. 

 

#include <bits/stdc++.h>

using namespace std;

int k = 7;
int n = 9;
int a[9];

void combi(int start, vector<int> b){
    if(b.size() == k){
        int sum = 0;
        for(int height : b) sum += height;

        if(sum == 100){
            sort(b.begin(), b.end());
            for(int height : b) cout << height << '\n';
            exit(0);
        }

        return;
    }


    for(int i = start + 1; i < n; i ++){
        b.push_back(a[i]);
        combi(i, b);
        b.pop_back();
    }

}



int main() {

    for(int i =0; i < n; i++) cin >> a[i];

    vector<int> b;
    combi(-1, b);


    return 0;
}

 

 

재귀함수를 통해 풀었는데, 3번정도 틀렸다.