[BaekJoon/백준] 2309번 일곱 난쟁이

 

 

나는 DFS로 9명의 난쟁이 중에 7명의 난쟁이를 뽑아서 계산했는데..

 

다른분들의 풀이를 보니 더 간단한 방법이 있었다.

전체 난쟁이의 합을 계산한 다음, 둘을 뺐을 때 100이 되는 경우를 찾으면 되는 것이다.

 

즉, 내 풀이는 9C7이었는데, 위 방법은 9C2로 해결할 수 있었다. 그럼 DFS처럼 재귀로 하지 않고 반복문으로 해도 풀 수 있겠다.

 

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

using namespace std;

vector<int> v;

vector<int> ans;

// 조합을 이용해서 9개 중에 7개를 뽑는다.
// 한 방향으로만 이동하니까, VISIT 확인은 굳이 해주지 않아도 될 거 같네.
// 넣었다 뺐다 토글만 잘 해주면 된다. (push - pop)

void dfs(int start) {
    
    if(ans.size() == 7) {
        
        int SUM = 0;
        
        for(int i = 0; i < 7; i++) {
            
            SUM += ans[i];
        }
        
        if(SUM == 100) {
            
            sort(ans.begin(), ans.end());
        
            for(int i = 0; i < 7; i++)
                cout << ans[i] << "\n";
            
            exit(0); // 찾았을 경우, exit 해줘야 한다.

        }
        
        return;
    }
    
    
    for(int i = start; i < 9; i++) {
        
        
        ans.push_back(v[i]);
        
        dfs(i + 1);
        
        ans.pop_back();
        
        
    }
    
    
}

int main() {
    
    int T = 9;
    int tmp;
    
    while(T--) {
        
        cin >> tmp;
        
        v.push_back(tmp);
        
        
    }
    
    dfs(0);
    
}

DFS로 풀 때 주의할 점은, 합이 100이되는 경우를 찾은 경우에는 return이 아니라 exit으로 프로그램을 종료해주어야 한다

(https://www.acmicpc.net/board/view/85586)

 

 

소요 시간 : 20분