[Algorithm] BOJ : 일곱 난쟁이

안녕하세요, iOS 개발하는 루피입니다.

 

오늘은 순열과 조합의 방식으로 백준 일곱 난쟁이 문제를 풀어보도록 하겠습니다.

 

바로 시작합니다.

---

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

이번 문제는 순열과 조합으로 접근하여 문제를 풀 수 있습니다. 순열과 조합에 대한 알고리즘은 익혀두고 있으면 좋을거 같습니다.

순열을 이용한 풀이

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

int main() {
    vector<int>v(9);

    for ( int i=0;i<9;i++) cin >> v[i];
    sort(v.begin(),v.end());

    do {
        int sum = 0;
        for (int i=0;i<7;i++) sum += v[i];
        if(sum == 100) break;
    } while(next_permutation(v.begin(), v.end()));

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

• next_permutation()을 이용해 매번 다른 순열을 만듭니다.
• 새로 만들어진 수열에서 0~6 까지의 요소의 합이 100 이 될 경우 빠져나오는 로직을 구현합니다.
• 이때 의도한대로 제일 작은 순열 부터 만들어 내기위해 이전에 sort문을 이용해 정렬하는 것이 중요합니다.

조합을 이용한 풀이

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

int sum = 0;
int arr[9];
vector<int>v;
pair<int, int> ret;

void solved(){
    for ( int i=0;i<9;i++) {
        for ( int j=0;j<i;j++) {
            if(sum-(arr[i]+arr[j])==100) {
                ret = {i,j};
                return;
            }
        }
    }
}

int main() {
    for ( int i = 0;i<9;i++) {
        cin >> arr[i]; sum += arr[i];
    }
    solved();
    for ( int i=0;i<9;i++) {
        if(ret.first == i || ret.second == i) continue;
        v.push_back(arr[i]);
    }
    sort(v.begin(),v.end());
    for( int i:v ) cout << i << '\n';
    return 0;
}

• 9개 중 7개를 뽑았을 때 합이 100이 되어야합니다.
• 이 말은 즉 9개중 2개를 뽑았을때, 전체합 - (2개 의 합) == 100이라는 말과 동일합니다.
• 9C7 = 9C2

---

오늘도 화이팅입니다.