[C++] 백준-2309 일곱 난쟁이

일곱 난쟁이 문제

---

아이디어?

이 문제의 아이디어는 "입력 받은 아홉 난쟁이의 키 중에서 두 난쟁이를 뺀 나머지 합이 100이 되는 경우를 찾는 것" 이다.

 

이를 위해서는 여러번 loop를 돌려야하는데, C++에는 next_permutation(순열)이라는 함수가 존재한다.

[ next_permutation ]

만약 {0, 1, 2} 라는 배열이 있다고 했을 때 이를 순열을 구한다면 아래와 같은 순열을 얻을 수 있다.

{0, 1, 2}
{0, 2, 1}
{1, 0, 2}
{1, 2, 0}
{2, 0 ,1}
{2, 1, 0}

단, 순열을 사용할 때는 오름차순으로 정렬 된 값을 가진 컨테이너만 사용가능하다.

 

해결하는 방법은?

우선 전체 코드를 보여주고 각 코드블럭을 설명하겠다.

#include <bits/stdc++.h>
using namespace std;  

int a[9]; 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    for(int i = 0; i < 9; i++){
        cin >> a[i]; 
    }
    
    sort(a, a + 9);
    
    do{
        int sum = 0; 
        for(int i = 0; i < 7; i++) sum += a[i]; 
        
        if(sum == 100)break;
    }while(next_permutation(a, a + 9)); 
    
    for(int i = 0; i < 7; i++) cout << a[i] << "\n"; 
    
    return 0;
}

---

1. 기본 셋팅으로 코딩테스트를 위해서 항상 하듯이 준비를 해둔다

#include <bits/stdc++.h>
using namespace std;

 

 

2. 9개의 숫자가 들어올거니까 장소를 준비해준다

int a[9];

 

3. 빠른 입출력을 위해서 셋팅해준다

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

 

4. for문을 돌면서 각각 a 배열 안에 넣어준다

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

 

5. next_permutation을 위해서 오름차순 정렬을 해준다

   sort(a, a + 9);

 

6. do ~ while 구문을 이용해서 next_permutation이 끝날 때 까지  do 안을 실행시키며, 이 때 100이 되면 break가 걸리게 한다

    do{
        int sum = 0; 
        for(int i = 0; i < 7; i++) sum += a[i]; 
        
        if(sum == 100)break;
    }while(next_permutation(a, a + 9));

 

7. cout을 통한 출력을 하고, 마지막은 return 0을 해준다

    for(int i = 0; i < 7; i++) cout << a[i] << "\n"; 
    
    return 0;
}