[코딩테스트] [프로그래머스] 주사위 고르기

문제

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

---

풀이

1. n개의 주사위 중, A와 B가 n/2개씩 주사위를 나누어 갖는 조합을 구한다.
   1-1. 주사위 조합을 구하기 위해 n개의 크기를 가진 comb 벡터를 선언한다.
   1-2. comb 벡터의 begin부터 절반까지 1로 채운다. comb 벡터에서 1인 index가 teamA에 포함될 주사위의 index이다.
   1-3. comb 벡터를 순회하며 comb[i]가 1일때 teamA에 push_back, 반대일 때 teamB에 push_back 해준다.
   1-4. prev_permutation 함수로 더 작은 순열이 없을 때까지 반복한다.

2. dfs를 활용하여 각 조합별 주사위끼리 눈의 합을 sumsA 벡터, sumsB 벡터에 저장한다.
   ex) 주사위 = [[1, 2], [2, 3], [3, 4], [4, 5]] / teamA = [0, 1], teamB = [2, 3] 라고 가정하자. A는 0, 1번째 주사위의 합 [1+2, 1+3, 2+2, 2+3]을 반환하고, B는 2, 3번째 주사위의 합 [3+4, 3+5, 4+4, 4+5]를 반환한다.

3. sumsB 벡터를 sort 함수로 정렬한다.
   3-1. sumsA 벡터를 순회하며 현재 값이 sumsB 벡터에서 몇번째 인덱스에 있는 요소보다 크거나 같은지 계산하고, winCount에 저장한다. 즉, sumsB 요소가 현재 sumsA 요소보다 큰 횟수가 몇번인지 확인할 수 있다.
   ex) sumsA = [3, 4, 4, 5], sumsB = [7, 8, 8, 9] 일 때, sumsB에서 3보다 같거나 큰 첫번째 인덱스는 0이다. sumsB 요소가 3보다 모두 크다는 것을 알 수 있다.

4. winCount와 최다 우승 횟수(bestWin)를 비교하여 갱신하고, 최적의 조합을 answer 벡터에 저장한다.

5. 주사위 번호는 1번부터 시작하기 때문에 answer 벡터를 순회하며 값을 1씩 증가시킨다.

---

코드

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

using namespace std;

vector<vector<int>> dice;

void dfs(int index, int sum, int size, vector<int>& sums, vector<int>& team)
{
    if(index == size)
    {
        sums.push_back(sum);
        return;
    }
    
    for(int face : dice[team[index]])
        dfs(index+1, sum+face, size, sums, team);
}

vector<int> getSums(vector<int>& team)
{
    vector<int> sums;
    dfs(0, 0, team.size(), sums, team);
    return sums;
}

vector<int> solution(vector<vector<int>> inDice) 
{
    dice = inDice;
    int diceCount = dice.size();
    
    long long bestWin = -1;
    vector<int> answer;
    
    vector<int> comb(diceCount, 0);
    fill(comb.begin(), comb.begin() + diceCount/2, 1);
    
    do
    {
        vector<int> teamA, teamB;
        for(int i=0; i<diceCount; i++)
        {
            if(comb[i] > 0)
                teamA.push_back(i);
            else
                teamB.push_back(i);
        }
        
        vector<int> sumsA = getSums(teamA);
        vector<int> sumsB = getSums(teamB);
        sort(sumsB.begin(), sumsB.end());
        
        long long winCount =0;
        for(int x : sumsA)
        {
            winCount += lower_bound(sumsB.begin(), sumsB.end(), x) - sumsB.begin();
        }
        
        if(winCount > bestWin)
        {
            bestWin = winCount;
            answer = teamA;
        }
        
    } while (prev_permutation(comb.begin(), comb.end()));
    
    for(int& i : answer)
        i++;
    
    return answer;
}