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

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

2309번: 일곱 난쟁이

---

이 문제는 아홉 난쟁이들 중 7명을 뽑아(조합)하여 키의 합이 100인 경우를 찾는 문제입니다.

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
 
using namespace std;
 
vector<int> childs; // 난쟁이 키 저장
vector<int> tmp; 
 
// 재귀함수를 이용해 전체 조합 탐색 - 백트래킹
void find(int depth){
 
    // 임시배열의 사이즈가 7(일곱난쟁이)면서 합이 100인 경우(accumulate()를 이용해 합 계산)
    if (tmp.size() == 7 &&  accumulate(tmp.begin(), tmp.end(), 0) == 100){
        // 일곱난쟁이를 찾은 경우 이므로 정렬 후 출력
        sort(tmp.begin(), tmp.end());
        for (size_t i = 0; i < tmp.size(); i++){
            cout << tmp[i] << endl;
        }
        exit(0); // 여러 경우가 있을 수 있으므로 종료
        return;
    }
    if (depth >= 9) // 탐색 범위를 벗어난 경우 return
        return;
 
    // 현재 depth의 난쟁이를 추가 후 재귀
    tmp.push_back(childs[depth]); 
    find(depth+1);
    // 현재 depth의 난쟁이를 제거 후 재귀
    tmp.pop_back();
    find(depth+1);
}
 
int main(){
    int c;
    for (size_t i = 0; i < 9; i++){
        cin >> c;
        childs.push_back(c);
    }
 
    find(0);
    return 0;
}

 

find() 함수에서 depth에 해당하는 난쟁이를 tmp 배열에 추가하고, tmp 배열의 사이즈가 7(난쟁이가 7명이 되는 경우)에 배열의 합을 확인합니다.

배열의 사이즈가 7이고, 배열의 합이 100인 경우는 정답인 경우입니다. 이 경우 난쟁이들의 키를 오름차순으로 정렬하고 출력한 후 프로그램을 종료합니다.