[BOJ] #2309 일곱 난쟁이

시간 제한	메모리 제한	정답 비율
2 초	128 MB	46.670%

 

2309번: 일곱 난쟁이

 

9명의 난쟁이들 중 진짜 난쟁이는 7명이다. 다행히 7명의 난쟁이들의 키의 합은 100임을 알고 있다. 9명의 난쟁이들이 주어졌을 때 진짜 난쟁이 7명을 찾아 출력하라!

 

메모리	시간
1998 KB	0 ms

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[10], flg;
vector<int> v;
void dfs(int idx, int sum) {
    if (idx > 9 || flg) return;
    if (v.size()==7) {
        if (sum == 100) {
            sort(v.begin(), v.end());
            for (int i = 0; i < 7; i++) {
                printf("%d\n", v[i]);
            }
            flg = 1;
        }
        return;
    }
    v.push_back(arr[idx]);
    dfs(idx + 1,  sum + arr[idx]);
    v.pop_back();
    dfs(idx + 1, sum);
}
int main() {
    for (int i = 0; i < 9; i++)
        scanf("%d", &arr[i]);
 
    dfs(0, 0);
 
    return 0;
}

 

스터디에서 피드백 받은 부분

함수 매개변수에 cnt 라는 값을 추가하여 vector에서 arr[idx]번째 인자를 뺄 때마다 cnt 를 1씩 증가시키도록 하여 cnt가 3이상일 때는 return 되게끔 하라.

이유는 난쟁이는 무조건 9명이 들어오고, 7명의 난쟁이만 선택해야 하므로 6명 이하의 난쟁이들의 키의 합은 볼 필요가 없다. 따라서 필요없는 탐색을 하지 않을 수 있다.