Baekjoon 2309

백준 2309 문제, 일곱 난쟁이

대표적인 Brute Forse 문제로, 모든 경우의 수를 탐색하는 방법이다.

따라서, 9명 중에 7명을 뽑아서 7명의 키의 합이 100이 되면 정답을 출력하면 되는 문제로 간단한 로직을 요구하는 문제이다.

9명 중에 7명을 뽑아서...

위의 조건을 보고 Combination으로 문제를 해결하였는데,

문제를 곧이 곧대로 풀기보다, 잘 살펴보면 한번 더 간단하게 풀어서 문제를 풀 수 있음을 깨달아 이를 기록하기 위해서 이번 포스팅을 작성하게 되었다.

다음은 내가 첫번째로 작성한 코드이다.

/* < BruteForce 문제 >
 * 난쟁이 키의 경우의 수를 모두 더함으로써 합이 100이 되는 것을 찾자.
 * => Combination
 */
#include <bits/stdc++.h>
using namespace std;

#define NUM     9
#define SUM     100

int height[NUM] = {0};
vector<int> answer;

int calc (int d) {
    int sum = 0;
    for (int i = 0; i < d; i++) {
        sum += answer[i];
    }
    return sum;
}

void combi(int depth, int r) 
{
    static bool flag = false;

    if (flag) return ;
    if (answer.size() == r) {
        if (calc(r) == SUM) {
            for (int i = 0; i < r; i++) {
                cout << answer[i] << '\n';
            }
            flag = true;
        }
        return ;
    }
    for (int i = depth + 1; i < NUM; i++) {
        answer.push_back(height[i]);
        combi(i, r);
        answer.pop_back();
    }
}

int main (void)
{
    /* input */
    for (int i = 0; i < NUM; i++) {
        cin >> height[i];
    }
    /* sort */
    sort(height, height + NUM);
    /* combination */
    combi(-1, 7);

    return 0;
}

나는 문제 조건 텍스트 그대로 9명 중 7명을 뽑아서 7명의 키를 모두 합하고 해당 키가 100이면 정답을 출력하는 방식으로 코드를 작성하였다.

하지만 나 말고 다른 사람들의 코드를 보니 똑같은 combination이지만, 조금 더 간단하게 코드를 작성할 수 있다는 사실을 깨달았다.

9명 중에 7명을 뽑는다는 의미를 조금 한발짝 뒤로 서서 다른 관점으로 보게 된다면 9명 중에 난쟁이가 아닌 2명을 뽑는다는 의미와 같다.

이는 다시 말하면 9명의 키를 모두 더한 후에, 2명을 골라서 합에서 뺀 값이 100이라면 그 두명이 난쟁이가 아니라는 의미와 동일하다.

따라서 코드는 다음과 같이 간단해 질 수 있다.

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

#define NUM     9
#define TOTAL   100


pair<int, int> solve(int sum, int* height)
{
    for (int i = 0; i < NUM; i++) {
        for (int j = i + 1; j < NUM; j++) {
            if ((sum - (height[i] + height[j])) == TOTAL) {
                return {i, j};
            }
        }
    }
    return {-1, -1};
}

int main (void)
{
    int sum = 0;
    int height[NUM];
    pair<int, int> p;
    vector <int> answer;

    /* input */
    for (int i = 0; i < NUM; i++) {
        cin >> height[i];
        sum += height[i];
    }

    p = solve(sum, height);

    for (int i = 0; i < NUM; i++) {
        if (i == p.first || i == p.second) continue ;
        answer.push_back(height[i]);
    }

    /* print answer */
    sort(answer.begin(), answer.end());
    for (int i = 0; i < answer.size(); i++) {
        cout << answer[i] << '\n';
    }
    
    return 0;
}

TIL
문제 풀기에 앞서지 말고, 어려운 문제를 어떻게 하면 더 쉽게 풀 수 있을 지 고민하자.