백준 일곱난쟁이 2309

1. 백준 일곱난쟁이 2309

2. 컴퓨팅적 스킬

• do while ~ (next_permutation)으로 계속해서 다음 조합의 경우의 수를 찾는다.
• vector v, check변수를 선언하여 permutation을 수행한다. 9명중 7명을 뽑아야하므로 7명만큼 check=true로 변경해서 수행한다. next_permutation을 수행하면서 값들이 계속변경되기 때문에 값이 변경되면서 출력된다.

3. 컴퓨팅적 사고

• 백설공주를 도와 키를 확인하여 난쟁이를 찾자. 9명의 난쟁이 중에 7명의 난쟁이를 골라 키의 합이 100이 되는 경우를 찾아야한다.
• 9명중에 7명을 고르는 것은 9C7 = 9C2와 같은 경우의 수이다.
• 9명중 2명을 골랐을때 두명을 고르는 수는 O(N^2) * 난쟁이의 키의 합을 고르는 복잡도 O(N) = O(N^3)의 시간복잡도를 갖는다. N=9명이므로 9^3 = 729의 모든경우의 수에서 찾을 수 있다.
• 경우 1)난쟁이가 아닌 9명중 2명을 뽑는 경우를 구해서 sum의 값에서 그 해당 값들을 뺐을때 합이 100인경우를 찾는다.
• 경우 2)next_permutation을 돌려서 9명중 7명을 선택해서 그 값이 100일때 그 값들을 출력시켜준다. 이때 check변수를 선언하여 7명을 선택해야하는 경우를 true로 바꾸어주면서 수행한다.

주의해야 할점: 정렬이 되어있는 상태여야 한다.

---

4. 풀이

4.1. 이중 포문

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
    
    int n = 9;
    int sum = 0;
    vector<int> v(n);
    
    for(int i=0; i<n; i++){
        cin >> v[i];
        sum += v[i];
    }
    
    sort(v.begin(), v.end());
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            if(sum - v[i] - v[j] == 100){
                for(int z=0; z<n; z++){
                    if(i == z || j == z){
                        continue;
                    }
                    cout << v[z] << '\n';
                    
                }
                break;
                
            }
        }
    }
    
    
    
    return 0;
}

4.2. next_permutation 조합

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
    int n = 9;
    vector<int> v(n);
    vector<bool> check(n);
    
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    for(int i=0; i<7; i++){
        check[i] = true;
    }
    sort(v.begin(), v.end());
    do {
        int sum = 0;
        for(int i=0; i<n; i++){
            if(check[i] == true){
                sum += v[i];
            }
        }
        
        if(sum== 100){
            for(int i=0; i<7; i++){
                cout << v[i] << "\n";
            }
            break;
        }
    } while (next_permutation(v.begin(),v.end()));
}