[백준] 2309 일곱 난쟁이 backtracking

문제 :

www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

분석 :

브론즈였음에도 어려웠다.. 앞으로 브루트 포스, 백트래킹쪽을 좀 더 공부해 보아야겠다.

종만북에서 보았던 아이디어를 가지고 문제 접근을 하였다.

각 난쟁이들은 100을 포함하는데 속하거나 안 속하거나 둘중 하나이다. 그러므로 모든 난쟁이들을 탐색하는데 return 문을 만나 재귀가 끝나게 되면 visit를 false로 해 속하지 않게끔 만들고 다른 원소들을 탐색하는 것이다. 

이렇게 하여 속하는 원소들만을 정렬해 출력한다.

 

C++ 코드 :

//
//  2309_dwarf7.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/04/06.
//

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


using namespace std;
vector<int>arr;
vector<int>re_arr;

int visit[100];
int cnt = 0;

void brute_dwarf7(int score, int cnt){
    if (score == 100 and cnt == 7){
        sort(re_arr.begin(), re_arr.end());
        
        for(int i = 0; i < 7; i++){
            cout << re_arr.at(i) << "\n";
        }
        exit(0);
    }
    
    if (cnt > 7 || score > 100){
        return;
    }
    
    for(int i= 0; i <9; i++){
        if(visit[arr[i]] == false){
            visit[arr[i]] = true;
            re_arr.push_back(arr[i]);
            brute_dwarf7(score + arr[i], cnt + 1);
            visit[arr[i]] = false;
            re_arr.pop_back();
        }
    }
    return;

}

int main(){
    memset(visit, false, sizeof(visit));
    for(int i =0; i < 9; i++){
        int temp;
        cin >> temp;
        arr.push_back(temp);
    }
    brute_dwarf7(0, 0);
    
    return 0;
}