이번 문제는 프로그래머스의 레벨 3 주사위 고르기 문제이다.
이 문제는 KAKAO 2024 인턴십 코딩테스트 문제였다.
그 때 당시에는 풀려고 시도했지만, 결국 풀지 못했다.

최대 10개의 주사위가 주어진다.
A와 B는 각자 n/2개의 주사위를 가져간다.
이후 모든 주사위를 던져 합이 크게 나온 쪽이 이기는 게임이다.
과연 A가 어떤 주사위를 가져가야 이길 확률이 가장 높을까?

이길 확률이 가장 높은 주사위가 유일한 케이스만 주어진다.
문제를 어떻게 풀 수 있을까?

Greedy?

시험 당시에는 그리디하게 풀려고 계속 접근했었다.
이길 수 있는 확률이 높은 주사위를 미리 판단해서 고르는게 맞다고 생각했다.
하지만 그 때 당시에는 문제를 풀지 못했다.

그리디 하게 풀기에는 생각해야 할 조건이 너무 많고 복잡했다.
시간이 부족해 생각을 넓게 하지 못한 것이 패착이라고 생각한다.

완전탐색!

사실, 너무 경우의 수가 많을 것 같아 완탐은 엄두도 내지 못했다.
그 때는 급하게 풀어서 그랬지만, 지금은 논리적으로 한 번 생각해보자.
완전탐색으로 풀었을 때 시간초과가 발생하지 않을까?

먼저 10개의 주사위 중 5개를 선택하는 경우는 10C5이다.
각 주사위는 6개의 수가 있으니, 합이 조합되는 경우는 6^5가지가 된다.
이 때, B의 조합도 생각을 해주어야 하니 2 * 6^5가지가 될 것이다.
즉 총 경우의 수는 2 * 6^5 * 10C5가 되는 것이다.

그 값은 15552 * 252 = 약 390만 정도가 된다.
즉, 시간초과가 발생하지 않을 정도의 계산이라는 말이 된다!
한 번 A가 모든 조합의 주사위를 가져갈 수 있도록 코드를 짜보자.

우선 주사위를 선택하는 로직은 아래와 같이 구현되었다.

void select_dice(int depth, int idx, int size, vector<vector<int>> &dice) {
    if (depth == size / 2) {
        // 여기서 비교 계산
        make_b_vec();
        calculate_sum(dice);

        a_sum_vec.clear();
        b_sum_vec.clear();
        b_dice_vec.clear();
        return;
    }

    for (int i = idx + 1; i < size; i++) {
        a_dice_vec.push_back(i);
        dice_info[i] = true;
        select_dice(depth + 1, i, size, dice);
        a_dice_vec.pop_back();
        dice_info[i] = false;
    }
}

이후, 각 주사위에 대해서 눈을 선택하는 로직을 구현했다.
주사위를 선택하는 로직과 동일하게 백트래킹을 이용했다.

void select_each_digit(int a_sum, int b_sum, int depth, int size, vector<vector<int>>& dice) {
    if (depth == size) {
        a_sum_vec.push_back(a_sum);
        b_sum_vec.push_back(b_sum);
        return;
    }

    for (int i = 0; i < 6; i++)
        select_each_digit(a_sum + dice[a_dice_vec[depth]][i], b_sum + dice[b_dice_vec[depth]][i], depth + 1, size, dice);
}

마지막으로 핵심인 합을 비교하는 로직을 아래와 같이 구현했다.
이 부분에서 로직의 시간 복잡도를 줄이는 것이 관건이었다.
처음에는 O(N^2)으로 그냥 계산을 하려 했었다.
하지만, 시간초과가 나게 되었고 다른 방법을 고민하게 되었다.

생각해보니 굳이 이중포문을 사용해서 모두 세어줄 필요가 없었다.
이미 정렬이 되어있으니, A와 B의 크기만 비교해주면 된다.
만약 A가 크다면? B의 현재 위치까지는 모두 이기는 것이다.
그러니 B가 A보다 같거나 커질 때까지 움직인다.
이후 B의 위치까지의 길이를 더해주면, A가 이기는 경우가 된다.

위의 경우를 A나 B의 포인터가 끝날 때 까지 반복하면 된다.
B가 먼저 끝난 경우는 남은 A에 대해서도 처리를 해준다.

int a_size = a_sum_vec.size();
int b_size = b_sum_vec.size();
sort(a_sum_vec.begin(), a_sum_vec.end());
sort(b_sum_vec.begin(), b_sum_vec.end());

int a_win_cnt = 0, a_ptr = 0, b_ptr = 0;
while (a_ptr < a_size && b_ptr < b_size) {
    if (a_sum_vec[a_ptr] > b_sum_vec[b_ptr])
                b_ptr++;
    else {
        a_win_cnt += b_ptr;
        a_ptr++;
    }
}

if (b_ptr == b_size)
// B의 합 탐색이 먼저 끝난 경우
    a_win_cnt += (b_ptr * (a_size - a_ptr));
// 어차피, A가 B의 길이 만큼 다 이기는 조합 밖에 안남음
// 그냥 A의 남은 수 * B의 길이 만큼 더해주면 됨

if (a_win_cnt > max_win_cnt) {
    answer_vec = a_dice_vec;
    max_win_cnt = a_win_cnt;
}

다행히 정답을 받았다!

image

역시 시간복잡도에 대한 걱정은 직접 계산해봄이 빠르다.
문제를 풀 때 가장 먼저 시간복잡도를 계산하는 습관을 기르자!