프로그래머스 : 주사위 고르기

문제

오늘의 챌린지 문제. 카카오 기출이다

풀이

이번 문제를 설명하자면 주사위가 N개 주어지고 각 주사위는 6면이 있고 각 면마다 숫자가 다르다

A와 B가 n / 2개의 주사위를 나눠가지고 나눠 가진 주사위를 모두 던져 주사위의 합을 구하고 A와 B가 그 합을 가지고 승부한다. 그래서 승리, 무승부, 패배의 수를 구해 A가 B에게 가장 큰 승률을 거둘 수 있는 주사위의 번호를 출력하는 문제이다

나는 다음과 같은 과정으로 문제에 접근했다

1. 주사위를 나눌 수 있는 조합을 구한다
2. 나눈 조합을 가지고 하나씩 테스트해본다
3. A와 B가 가지고 있는 주사위 목록을 업데이트
4. A와 B가 가진 주사위로 구할 수 있는 합을 구한다
5. A의 합 벡터를 순회하며 B의 합 벡터와 비교하며 승리, 무승부, 패배를 구한다
6. 승률을 구해 정답 벡터를 업데이트한다

가장 먼저 1번에서는 흔한 재귀를 이용한 조합 구하기로 vector<vector<int>> selectDice에 가능한 주사위 조합을 구한다

2번에서 selectDice를 순회할건데 이 때 최적화를 위해 selectDice의 반만큼 순회한다

예를 들어 주사위 4개가 있을 때 주사위를 나눌 수 있는 방법은 (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)인데 앞의 3개의 조합을 이용할 때 뒤의 3개의 조합은 자동으로 B가 가지고 있는 주사위들이기에 뒤의 3개의 조합도 저절로 승률을 구할 수 있다

3번은 그냥 선택한 주사위를 A와 B 각각에게 배분해준다

4번은 각자 가진 주사위들을 던져 나올 수 있는 합을 구해야 하는데 최대 5개 주사위까지 가질 수 있으니 반복문을 쓰기는 애매해서 재귀를 사용했다

이 문제를 풀면서 인덱스 관리가 좀 중요했다. 집중하면서 풀자

4번을 통해 A와 B의 합 벡터를 만들었는데 이제 승률을 구해야 한다. A와 B 이중 반복문을 통해 승률을 구하는건 시간복잡도가 안 좋기 때문에 lower_bound와 upper_bound를 이용한 이분 탐색을 사용했다

B의 합 벡터를 정렬 후 A의 합을 돌면서 승리, 무승부, 패배를 구할 수 있는 공식을 사용했다

승리, 무승부, 패배의 횟수를 구하고 나서 승률을 구하는데 여기서 승률을 2개로 나눴다. A의 승률과 B의 승률을 나눴는데 만약 B의 승률이 A의 승률보다 높고 최대 승률보다 높으면 정답 벡터를 그냥 B의 주사위 목록으로 업데이트 하면 되기 때문이다

그렇게 정답 벡터를 출력해주면 끝

코드

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

int N;
vector<vector<int>> selectDice;
vector<vector<int>> indexCombi;

float prob;

void Combi(int start, int depth, vector<int>& A_dices)
{
    if(A_dices.size() == depth)
    {
        selectDice.push_back(A_dices);
        return;
    }
    
    for(int i = start; i < N; i++)
    {
        A_dices.push_back(i);
        Combi(i + 1, depth, A_dices);
        A_dices.pop_back();
    }
}

void DiceSum(vector<vector<int>>& dice, vector<int>& select, int idx, int sum, vector<int>& result)
{
    if(idx == select.size())
    {
        result.push_back(sum);
        return;
    }
    
    for(int i = 0; i < 6; i++)
    {
        DiceSum(dice, select, idx + 1, sum + dice[select[idx]][i], result);
    }
}

vector<int> solution(vector<vector<int>> dice) {
    vector<int> answer;
    
    N = dice.size();
    
    // 주사위를 선택하는 조합
    // selectDice 초기화
    vector<int> v;
    Combi(0, N / 2, v);
    
    // 주사위를 나눈 경우의 수
    for(int i = 0; i < (int)selectDice.size() / 2; i++)
    {
        // A와 B가 나눈 주사위를 먼저 구함
        vector<int> A, B;
        
        for(int j = 0; j < N; j++)
        {
            if(find(selectDice[i].begin(), selectDice[i].end(), j) != selectDice[i].end())
            {
                A.push_back(j);
            }
            else
            {
                B.push_back(j);
            }
        }
        
        vector<int> A_result;
        vector<int> B_result;
        
        DiceSum(dice, A, 0, 0, A_result);
        DiceSum(dice, B, 0, 0, B_result);
        
        sort(B_result.begin(), B_result.end());
        
        int victory = 0;
        int draw = 0;
        int defeat = 0;
        
        for(int A_sum : A_result)
        {
            auto lower = lower_bound(B_result.begin(), B_result.end(), A_sum);
            auto upper = upper_bound(B_result.begin(), B_result.end(), A_sum);
            
            victory += (lower - B_result.begin());
            draw += (upper - lower);
            defeat += (B_result.end() - upper);
        }
        
        float prob1 = (float)victory / (victory + draw + defeat);
        float prob2 = (float)defeat / (victory + draw + defeat);
        
        if(prob1 > prob2)
        {
            if(prob < prob1)
            {
                prob = prob1;
                answer = A;
            }
        }
        else
        {
            if(prob < prob2)
            {
                prob = prob2;
                answer = B;
            }
        }
    }
    
    for(int i = 0; i < answer.size(); i++)
    {
        answer[i]++;
    }
    
    return answer;
}

회고

어우 너무 복잡하게 푼 문제같다. 재귀를 두 번(조합, 주사위 합)이나 사용하고 또 이분탐색까지 생각했어야 했다

내 실수로는 합이 중복이 많이 돼서 시간 복잡도가 안 좋을까봐 set을 사용했는데 이러면 승률 계산이 이상해져서 답이 이상하게 나왔다. 그냥 vector를 사용했다