프로그래머스[Lv.3] - 주사위 고르기

 

 

문제 설명

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

---

 

 

 

 

 

 

풀이

처음에는 조합을 여러 번 쓰는 문제라고 생각했다.

풀던 중 시간 복잡도때문에 멈칫하는 부분이 있었지만, 그대로 진행했다.

역시나 시간초과가 발생했다.

처음에는 주사위를 고르는 경우의 수와 고른 주사위를 굴렸을 때 나오는 경우의 수를 모두 구해 이기는 경우를 구했었다.

이렇게 풀면 테스트케이스 중 제일 밑에 5개(?) 정도 시간초과가 발생한다.

 

시간을 줄이려면 승리 판정 부분에서 약간의 트릭이 필요하다.

처음에는 모든 경우를 하나하나 비교했기 때문에  주사위를 고르는 경우의 수 * 주사위를 굴렸을 때 나오는 경우의 수 만큼의 연산이 필요하다.

이 부분을 이진 탐색을 이용해 줄일 수 있다.

이 문제에서는 어떤 주사위의 수가 무엇인지는 중요하지 않다.

중요한 건 고른 주사위의 눈을 모두 더한 값이다.

따라서, 결괏값들을 모두 구한 뒤 정렬하여 상대의 결괏값들을 몇 개나 이길 수 있는지 구하면 된다.

이때, 이진 탐색을 이용하면 짧은 시간에 구할 수 있다.

상대의 결과들을 이긴 승수가 가장 큰 주사위의 조합을 답으로 채택하면 된다.

 

이진 탐색: lower_bound(begin, end, n) → n보다 크거나 같은 첫 번째 포인터

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

void Roll(int currentSum, vector<int>& rollSum, int depth, vector<int>& picks, vector<vector<int>>& dice)
{
    if(depth == picks.size())
    {
        rollSum.push_back(currentSum);
        return;
    }
    
    for(int i = 0; i < 6; i++)
    {
        currentSum += dice[picks[depth]][i];
        Roll(currentSum, rollSum, depth+1, picks, dice);

        currentSum -= dice[picks[depth]][i];
    }
}

vector<int> solution(vector<vector<int>> dice) {
    vector<int> answer;
    
    //완탐
    //n개중 n/2개 고르기
    vector<vector<int>> APicks;
    vector<vector<int>> BPicks;
    
    vector<int> temp;
    vector<vector<int>> roll;
    
    for(int i = 0; i < (1 << dice.size()); i++)
    {
        vector<int> AtempPick;
        vector<int> BtempPick;
        
        for(int j = 0; j < dice.size(); j++)
        {
            if(i & (1 << j)) AtempPick.push_back(j);
            else BtempPick.push_back(j);
        }
        
        if(AtempPick.size() == BtempPick.size())
        {
            APicks.push_back(AtempPick);
            BPicks.push_back(BtempPick);
        }
    }
    
    
    int maxWin = 0;
    vector<int> candidate;
    
    for(int i = 0; i < APicks.size(); i++)
    {
        vector<int> ASums;
        Roll(0, ASums, 0, APicks[i], dice);
        
        vector<int> BSums;
        Roll(0, BSums, 0, BPicks[i], dice);
        
        sort(ASums.begin(),ASums.end());
        sort(BSums.begin(),BSums.end()); 
        
        int winRate = 0;
        for(int n : ASums){
            int win = lower_bound(BSums.begin(), BSums.end(), n) - BSums.begin(); 
            if(win - 1 > 0) winRate += win; 
        }
        
        if(winRate > maxWin)
        {
            maxWin = winRate;
            candidate = APicks[i];
        }
    }
    
    
    
    for(int i = 0; i < candidate.size(); i++)
    {
        answer.push_back(candidate[i]+1);
    }
    
    return answer;
}

---