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

문제

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

해설

입력값이 9개 밖에 되지 않아 전부 순열을 돌려도 그리 큰 수가 아니기에 순열을 통해 0~6까지의 인덱스에 위치한 값들의 합이 100이 되면 do-while문 종료 후 정렬 후 리턴

 

코드

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int a;
    int arr[9];
    for(int i = 0; i<9;i++){
        cin >> a;
        arr[i] = a;
    }
    sort(arr,arr+9);
    do{
        int sum = accumulate(arr,arr+7,0);
        if(sum == 100) {
            sort(arr,arr+7);
            cout << "\n\n";
            for(int i=0 ; i<7; i++) {
            cout << arr[i] << "\n";
            }
            break;
        }
    }while(next_permutation(arr,arr+9));
    return 0;
}

추가 방법

• 순열을 이용하면 경우의 수가 줄어들어 더 빠르게 가능
• 매번 0~6까지의 합을 구하는 것이 아닌 (전체합 - 가짜난쟁이2명) = 100 이 되는 경우 찾기도 가능