2309

백준 2309번

Link: 2309번: 일곱 난쟁이

---

문제 설명

평범하게 모든 경우를 따져가며 조건 맞으면 출력해주는 DFS 문제였다.

9개 중 7개를 뽑아 합이 100이 될때 리턴해주면 되는 문제다.

요즘 DFS를 활용한 완전탐색 문제를 많이 접하는 것 같다.

이건 그중에서도 기초적인 문제인듯 하다.

분명 방학 시작 전까지는 이런 쉬운 문제도 쩔쩔매며 어떻게 풀지 고민했을 것 같은데, 어느새 아 이거 DFS로 조합 구해서 풀면 되는 문제네 하고 떠오를 수준이 되었다는 점이 마냥 신기하다.

이런식으로 DP도 정복하는 것이 목표이다.

---

정답 코드

//
// Created by Keith_Lee on 11/02/2019.
//

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int littles[9] = {0, };
bool visit[9] = {false, };
vector<int> intermediate;

void DFS(int index, int count){
    if(index == 9){
        if(count == 7){
            int sum = 0;

            for(int i=0; i<9; i++){
                if(visit[i]){
                    sum += littles[i];
                }
            }

            if(sum == 100){
                for(int i=0; i<9; i++){
                    if(visit[i]){
                        intermediate.push_back(littles[i]);
                    }
                }
            }
        }

        return;
    }

    visit[index] = true;
    DFS(index+1, count+1);
    visit[index] = false;
    DFS(index+1, count);
}

int main(){
    for(int i=0; i<9; i++){
        cin >> littles[i];
    }

    DFS(0, 0);

    vector<int> result;

    for(int i=0; i<7; i++){
        result.push_back(intermediate[i]);
    }

    sort(result.begin(), result.end());

    for(int i=0; i<result.size(); i++){
        cout << result[i] << '\n';
    }

    return 0;
}

---