[Programmers] 주사위 고르기 [C++]

https://school.programmers.co.kr/learn/courses/30/lessons/258709

문제 설명

A와 B가 n개의 주사위를 가지고 승부를 합니다. 주사위의 6개 면에 각각 하나의 수가 쓰여 있으며, 주사위를 던졌을 때 각 면이 나올 확률은 동일합니다. 각 주사위는 1 ~ n의 번호를 가지고 있으며, 주사위에 쓰인 수의 구성은 모두 다릅니다.

A가 먼저 n / 2개의 주사위를 가져가면 B가 남은 n / 2개의 주사위를 가져갑니다. 각각 가져간 주사위를 모두 굴린 뒤, 나온 수들을 모두 합해 점수를 계산합니다. 점수가 더 큰 쪽이 승리하며, 점수가 같다면 무승부입니다.

A는 자신이 승리할 확률이 가장 높아지도록 주사위를 가져가려 합니다.

다음은 n = 4인 예시입니다.

주사위 구성

#1	[1, 2, 3, 4, 5, 6]
#2	[3, 3, 3, 3, 4, 4]
#3	[1, 3, 3, 4, 4, 4]
#4	[1, 1, 4, 4, 5, 5]

• 예를 들어 A가 주사위 #1, #2를 가져간 뒤 6, 3을 굴리고, B가 주사위 #3, #4를 가져간 뒤 4, 1을 굴린다면 A의 승리입니다. (6 + 3 > 4 + 1)

A가 가져가는 주사위 조합에 따라, 주사위를 굴린 1296가지 경우의 승패 결과를 세어보면 아래 표와 같습니다.

 

A의 주사위 승 무 패

#1, #2	596	196	504
#1, #3	560	176	560
#1, #4	616	184	496
#2, #3	496	184	616
#2, #4	560	176	560
#3, #4	504	196	596

A가 승리할 확률이 가장 높아지기 위해선 주사위 #1, #4를 가져가야 합니다.

주사위에 쓰인 수의 구성을 담은 2차원 정수 배열 dice가 매개변수로 주어집니다. 이때, 자신이 승리할 확률이 가장 높아지기 위해 A가 골라야 하는 주사위 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 승리할 확률이 가장 높은 주사위 조합이 유일한 경우만 주어집니다.

제한사항

• 2 ≤ dice의 길이 = n ≤ 10
  • n은 2의 배수입니다.
  • dice[i]는 i+1번 주사위에 쓰인 6개의 수를 담고 있습니다.
  • dice[i]의 길이 = 6
  • 1 ≤ dice[i]의 원소 ≤ 100

입출력 예시

dice result

[[1, 2, 3, 4, 5, 6], [3, 3, 3, 3, 4, 4], [1, 3, 3, 4, 4, 4], [1, 1, 4, 4, 5, 5]]	[1, 4]
[[1, 2, 3, 4, 5, 6], [2, 2, 4, 4, 6, 6]]	[2]
[[40, 41, 42, 43, 44, 45], [43, 43, 42, 42, 41, 41], [1, 1, 80, 80, 80, 80], [70, 70, 1, 1, 70, 70]]	[1, 3]

문제 해석

1. A가 승리할 확률을 최대로 만들기 위해 최적의 주사위 선택을 해야 한다
2. 주사위 조합을 만들어야 한다
3. 만들어진 주사위 조합 내에서 각각 합의 조합을 구하여야 한다
4. 승패 시뮬레이션을 해야 한다
5. 중복된 숫자가 있을 수 있다

코드

void dfs(int idx, int N, int target, vector<vector<int>>& comb, vector<int>& container){
    if(container.size() == target){
        comb.push_back(container);
        return;
    }

    for(int i = idx; i<N; i++){
        container.push_back(i+1);
        dfs(i + 1, N, target, comb, container);
        container.pop_back();
    }
}

• 완전탐색을 이용한 주사위 조합 생성 함수
• N/2 개의 주사위를 선택하는 모든 경우의 수를 생성

void calcSum(int idx, int currentSum, vector<int>& tmp, vector<int>& currentComb, vector<vector<int>> dice){
    if(idx == currentComb.size()){
        tmp.push_back(currentSum);
        return;
    }

    for(int i = 0; i< dice[currentComb[idx] - 1].size(); i++){
        currentSum += dice[currentComb[idx] - 1][i];
        calcSum(idx + 1, currentSum, tmp, currentComb, dice);
        currentSum -= dice[currentComb[idx] - 1][i];
    }
}

• 주사위 합 계산 함수
• 주어진 주사위 조합에 대해 가능한 모든 주사위의 합을 계산

while(start < end){
    // ... (코드 중략)
    
    for(auto n : tmp1){
        int win = lower_bound(tmp2.begin(), tmp2.end(), n) - tmp2.begin();
        if(win >= 0) win1 += win;
    }
    for(auto n : tmp2){
        int win = std::lower_bound(tmp1.begin(), tmp1.end(),n) - tmp1.begin();
        if(win >= 0) win2 += win;
    }

    if(win1 > win2 && win1 > maxWin){
        answer = comb[start];
        maxWin = win1;
    }else if(win2 > win1 && win2 > maxWin){
        answer = comb[end];
        maxWin = win2;
    }
    // ... (코드 중략)
}

• 두 조합간의 승리 횟수를 계산
• 정렬 후 lower_bound 를 사용하여 같거나 작은 합의 수를 계산

전체코드

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

void dfs(int idx, int N, int target, vector<vector<int>>& comb, vector<int>& container){
    if(container.size() == target){
        comb.push_back(container);
        return;
    }

    for(int i = idx; i<N; i++){
        container.push_back(i+1);
        dfs(i + 1, N, target, comb, container);
        container.pop_back();
    }
}

void calcSum(int idx, int currentSum, vector<int>& tmp, vector<int>& currentComb, vector<vector<int>> dice){
    if(idx == currentComb.size()){
        tmp.push_back(currentSum);
        return;
    }

    for(int i = 0; i< dice[currentComb[idx] - 1].size(); i++){
        currentSum += dice[currentComb[idx] - 1][i];
        calcSum(idx + 1, currentSum, tmp, currentComb, dice);
        currentSum -= dice[currentComb[idx] - 1][i];
    }
}

vector<int> solution(vector<vector<int>> dice) {
    vector<int> answer;
    vector<vector<int>> comb;
    vector<int> container;
    int N = dice.size();
    int target = N/2;

    dfs(0, N, target, comb, container);

    int start = 0, end = comb.size() - 1;
    int maxWin = 0;

    while(start < end){
        int sum1 = 0, sum2 = 0, win1= 0, win2 = 0;
        vector<int> tmp1, tmp2;
        calcSum(0, sum1, tmp1, comb[start], dice);
        calcSum(0, sum2, tmp2, comb[end], dice);

        std::sort(tmp1.begin(), tmp1.end());
        std::sort(tmp2.begin(), tmp2.end());

        for(auto n : tmp1){
            int win = lower_bound(tmp2.begin(), tmp2.end(), n) - tmp2.begin();
            if(win >= 0) win1 += win;
        }
        for(auto n : tmp2){
            int win = std::lower_bound(tmp1.begin(), tmp1.end(),n) - tmp1.begin();
            if(win >= 0) win2 += win;
        }

        if(win1 > win2 && win1 > maxWin){
            answer = comb[start];
            maxWin = win1;
        }else if(win2 > win1 && win2 > maxWin){
            answer = comb[end];
            maxWin = win2;
        }
        tmp1.clear();
        tmp2.clear();
        start++;
        end--;

    }

    return answer;
}