프로그래머스 문제 - 주사위 고르기

프로그래머스 주사위 고르기 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

A와 B가 n개의 주사위를 가지고 승부를 합니다.
주사위의 6개 면에 각각 하나의 수가 쓰여 있으며, 주사위를 던졌을 때 각 면이 나올 확률은 동일합니다.
A가 먼저 n/2개의 주사위를 가져가고, 이후에 B가 n/2개의 주사위를 가져갑니다.
각각 가져간 주사위를 모두 굴린 뒤, 나온 수들을 모두 합해 점수를 계산하며, 점수가 더 큰 쪽이 승리, 같다면 무승부입니다.
A가 승리할 확률이 가장 높아지도록 주사위를 가져가려고 하며, 승리할 확률이 가장 높은 주사위 조합을 구해야합니다.

문제 풀이

n/2개의 주사위로 나오는 모든 조합 중 승리할 확률이 가장 높은 주사위 조합을 찾아야 하기 때문에 순열 탐색을 사용하여 모든 주사위 조합을 찾아줍니다.
C++에서는 do-while과 함께 next_permutation이라는 함수를 사용하는데, 함수에 배열의 시작점과 끝점을 넣어주면 그 배열에서 중첩되지 않은 모든 배열을 사전순으로 바꿔줍니다.
위의 함수를 사용하기 위해서는 오름차순으로 되어 있어야 하기에 함수를 사용하기 전, 오름차순으로 정렬해 준 후 사용합니다.
n개의 주사위가 주어졌을 때 n/2개의 주사위를 선택하여 조합하기 때문에 1~n까지의 주사위를 n/2개씩 고르며, 중첩되지 않는 모든 순열을 검색해주면 됩니다.
순열을 사용해 A가 주사위를 선택했다면 나머지 주사위는 B가 던지게 됩니다.
여기서 주의할 점은 n이 홀수라면 B가 가진 주사위가 n/2보다 1개 더 많아지게 되므로, B가 가진 주사위를 n/2개씩 고르며, 중첩되지 않는 수열을 한 번 더 검색 후 진행해주면 됩니다.

A와 B의 주사위를 전부 선택했다면, 각 주사위를 굴린 모든 경우를 계산하여 배열에 저장해줍니다.
그러면 2개의 배열이 나오게되는데, 두 배열의 값들을 비교하여 승리, 무승부의 수를 구해주면 됩니다.
패배는 구하지 않아도 정답을 구해낼 수 있습니다.

모든 순열을 체크하며 승리의 수가 제일 큰, 같다면 무승부가 더 큰 상황의 주사위를 저장하여 반환해주면 됩니다.

전체 코드

순열 사용을 많이 해보지 않아 생각보다 어려운 문제였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<vector<int>> dices;
int n;

vector<int> dfsArray;
map<vector<int>, vector<int>>::iterator iter;

void dfs(vector<int> a, int index, int sum) //각 주사위를 굴린 모든 경우 계산
{
    if(a.size() == index){
        dfsArray.push_back(sum);
        return;
    }
    
    for(int i = 0; i < 6; i++)
    {
        sum += dices[a[index]-1][i];
        dfs(a, index+1, sum);
        sum -= dices[a[index]-1][i];
    }
}

vector<int> checkWin(vector<int> a, vector<int> b)  //A와 B가 굴린 주사위들의 합들을 가지고 승패 계산
{
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    vector<int> v(3, 0);
    
    int AIndex = 0;
    int BIndex = 0;
    int win = 0;
    int draw = 0;
    while(AIndex < a.size())
    {
        if(a[AIndex] > b[b.size()-1])   //A주사위값이 B주사위 중 제일 큰 값보다 더 크다면 
        {
            v[0] += b.size();
            AIndex++;
        }
        else if(a[AIndex] < b[BIndex])  //A가 더 클 경우
        {
            v[0] += win;
            AIndex++;
        }else if(a[AIndex] == b[BIndex])    //같으면 무승부로 처리
        {
            int t = b[BIndex];
            while(t == b[BIndex])
            {
                draw++;
                BIndex++;
            }
            t = a[AIndex];
            while(t == a[AIndex])
            {
                v[0] += win;
                v[1] += draw;
                AIndex++;
            }
            win += draw;
            draw = 0;
        }else   //B가 더 클 경우
        {
            int t = b[BIndex];
            while(t == b[BIndex])
            {
                win++;
                BIndex++;
            }
        }
    }
    
    return v;
}

vector<int> solve() //주어진 주사위들로 순열을 만들어줌
{
    //주사위에 번호 생성
    vector<int> vec(dices.size(), 0);
    for(int i = 0; i < dices.size(); i++)
    {
        vec[i] = i+1;
    }
    //순열을 위한 배열
    vector<int> ADice(dices.size(), 1);
    vector<int> BDice(dices.size() - n, 1);
    vector<int> AComb;
    vector<int> BComb;
    
    pair<int, int> maxWin = make_pair(0, 0);
    vector<int> result;
    
    for(int i = 0; i < n; i++)  //A와 B가 가질 주사위의 수 n/2 만큼 0으로 변환
    {
        ADice[i] = 0;
        BDice[i] = 0;
    }
    do{ //next_permutation과 0,1로 이루어진 배열을 가지고 중첩되지 않는 순열 생성
        vector<int> v1;
        vector<int> v2;
        vector<int> v3;
        for(int i = 0; i < ADice.size(); i++)
        {
            if(ADice[i] == 0)   //A의 주사위
                v1.push_back(vec[i]);
            else    //B의 주사위
                v2.push_back(vec[i]);
        }
        if(v2.size() > n)   //만약 주어진 주사위가 홀수라면
        {
            do{ //B의 주사위 중 n/2만큼만 선택
                for(int j = 0; j < BDice.size(); j++)
                {
                    if(BDice[j] == 0)
                    {
                        v3.push_back(v2[j]);
                    }
                }
                //A와 B의 각 주사위를 굴린 모든 경우 계산
                dfsArray = vector<int>();
                dfs(v1, 0, 0);
                AComb = dfsArray;
                dfsArray = vector<int>();
                dfs(v3, 0, 0);
                BComb = dfsArray;
                //승리, 무승부 횟수 게산
                vector<int> check = checkWin(AComb, BComb);
                if(maxWin.first < check[0] || maxWin.first == check[0] && maxWin.second < check[1])
                {
                    maxWin = make_pair(check[0], check[1]);
                    result = v1;
                }
            } while(next_permutation(BDice.begin(), BDice.end()));
        }else{
            //A와 B의 각 주사위를 굴린 모든 경우 계산
            dfsArray = vector<int>();
            dfs(v1, 0, 0);
            AComb = dfsArray;
            dfsArray = vector<int>();
            dfs(v2, 0, 0);
            BComb = dfsArray;
            //승리, 무승부 횟수 게산
            vector<int> check = checkWin(AComb, BComb);
            if(maxWin.first < check[0] || maxWin.first == check[0] && maxWin.second < check[1])
            {
                maxWin = make_pair(check[0], check[1]);
                result = v1;
            }
        }
    } while(next_permutation(ADice.begin(), ADice.end()));
    
    //제일 승리의 수가 크고, 그다음으로 무승부의 수가 큰 수를 반환
    return result;
}

vector<int> solution(vector<vector<int>> dice) {
    vector<int> answer;
    dices = dice;
    n = dice.size() / 2;    //주사위를 가져야하는 수
    
    answer = solve();
    
    return answer;
}

출저

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