백준 2309 일곱난쟁이 (C++)

* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다

 

백준 스페셜 저지 일곱난쟁이 풀이입니다

 

문제 해석

문제를 간단히 해석해보겠습니다

일과를 마치곤온 백설공주 앞에 난쟁이가 아홉명이 있었습니다, 이 아홉명의 난쟁이는 모두 자신이 일곱난쟁이라고 주장을했지만, 다행이도 백설공주는 일곱난쟁이의 키의 합이 100인것을 알고있었습니다

 

따라서 아홉 일곱난쟁이의 키가 주어졌을때 위에 조건에따른 일곱난쟁이를 구하는 문제입니다

 

여기서 중요한 부분은 아홉명의 일곤난쟁이중 7명을 뽑아 키의 합이 100인지를 확인하는것이 이문제의 핵심입니다

즉 순열 혹은 조합을 활용하여 풀수가있습니다 해당 글에서는 순열로 풀이하였습니다

 

문제 풀이 순서

1. 우선 9개의 정수를 배열로 입력받습니다

2. 순열로 풀것이기 때문에 입력받은 배열을 정렬해줍니다

3. 정렬한 배열에서 7개의 정수를 뽑습니다

4. 뽑은 7개의 정수합이 100인지를 체크합니다

5. 만약 정수의 합이 100일경우 3번에서 뽑은 7개의 정수를 출력하고, 아닐경우 3번으로 다시 돌아가 3,4,5번을 다시 진행합니다

 

작성 코드

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

int arr[9],sum;
int main(){

    //9개의 정수를 입력 받는다
    for(int i = 0; i < 9; i++){
        cin >> arr[i];
    }
    //순열을 정렬이 되어있어야 되기때문에 정렬을 한다,또한 문제에 오름차순이라고 되어있다
    sort(arr,(arr+9));
    //next_permutation 함수로 9개의 숫자에 대한 순열을 뽑는다
    do{
        //뽑아진 순열에서 7개를 가져와 sum에 더해준다
        sum = 0;
        for(int j = 0; j < 7; j++){
            sum += arr[j];
        }  

        //만약 sum에 합이 100일때 해당 순열을 출력하고 종료한다
        if(sum == 100){
            for(int j = 0; j < 7; j++){
                cout << arr[j] << "\n";
            }   
            break;
        }
    }while(next_permutation(arr,(arr+9)));
    

    
    return 0;
}

 

참고사항

저는 순열을 사용하여 7개의 정수의 합이 100인지를 체크하여 풀었지만

9개의 정수를 모두 더한후, 2개의 정수를 빼었을때 100인지를 체크하는 풀이도 있습니다