[ 프로그래머스 ] 주사위 고르기 (C++)

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

 

 A가 먼저 n / 2개의 주사위를 가져가고, B가 남은 n / 2개의 주사위를 가져가는 경우의 수는 최대 ₁₀C₅=252이고, A와 B가 가져간 주사위를 모두 굴려서 나오는 결과의 합을 구하는 경우의 수는 최대 6⁵, 약 7700이다.

 

 따라서, 완전 탐색을 이용해 A와 B가 주사위를 n / 2개 씩 가져가는 모든 경우에 대해 A와 B가 각각 가져간 주사위를 굴려서 나오는 모든 결과의 합을 구한 뒤 서로 비교하여 A가 승리하는 횟수가 가장 많은 경우를 찾아 문제를 해결할 수 있다. (252 x 7700은 약 200000)

 

 

[ 문제 풀이 ]

1. 가져갈 주사위를 고르는 기능

  - 완전 탐색을 이용해 A가 먼저 n / 2개의 주사위를 가져가고, B가 남은 n / 2개의 주사위를 가져가는 경우를 모두 탐색한다.

 

2. A, B가 가져간 주사위 조합에 따라 주사위를 굴린 결과의 합을 구하는 기능

  - 완전 탐색을 이용해 A와 B가 가져간 주사위(각각 최대 5개)를 굴렸을 때, 각각 주사위를 굴린 결과의 합을 모두 구하여 순서대로 오름차순으로 vector에 저장한다.

 

3. A가 승리할 확률을 구하는 기능

  - 위에서 구한 결과를 저장한 vector와 이진 탐색을 이용해 A가 이기는 횟수를 구한다.

      - lower_bound()를 이용하기 위해 vector를 정렬해야 하므로 O(n log n)의 시간복잡도가 필요. (200,000 log 200,000은 약 3,500,000)

 

[ 회고 ]

 완전 탐색을 이중으로 구현해야 했기 때문에 구현이 어려웠지만, 미리 정리해둔 접근 방법을 따라가며 침착하게 구현 방법을 생각하고, 수정하며 올바르게 구현하여 문제를 해결할 수 있었다.

 

[ 정답 코드 ]

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <math.h>

using namespace std;

int N;
map<int, int> choice;
int maxWin;
vector<int> result;
vector<vector<int>> aux;
int cnt;

void sumBf(int idx, const vector<int>& v, int sum, vector<int>& sums) {
    
    if(idx >= v.size()) {
        sums.push_back(sum);
        return;
    }
    
    for(int i = 0; i < aux[v[idx]].size(); i++) {
        sumBf(idx+1, v, sum+aux[v[idx]][i], sums);
    }
}

void calc(vector<int>& A, vector<int>& B) {
        
    vector<int> aSum;
    vector<int> bSum;
    
    sumBf(0, A, 0, aSum);
    sumBf(0, B, 0, bSum);
    
    sort(aSum.begin(), aSum.end());
    sort(bSum.begin(), bSum.end());
    
    int win = 0;
    
    for(int i = 0; i < aSum.size(); i++) {
        
        win += upper_bound(bSum.begin(), bSum.end(), aSum[i]) - bSum.begin();
    }
    
    if(maxWin < win) {
        maxWin = win;
        result = A;
    }
    
    vector<int>().swap(aSum);
    vector<int>().swap(bSum);
}

void bf(int idx, const vector<vector<int>>& dice, vector<int>& A, vector<int>& B) {
    
    if(A.size() < N/2) {
        for(int i = idx; i < N; i++) {
            A.push_back(i);
            choice[i]++;
            bf(i+1, dice, A, B);
            A.pop_back();
            choice[i]--;
        }
    } else {
        for(int i = 0; i < N; i++) {
            if(!choice[i]) {
                B.push_back(i);
            }
        }
        
        calc(A, B);
        vector<int>().swap(B);
    }
}

vector<int> solution(vector<vector<int>> dice) {
    vector<int> answer;
    
    N = int(dice.size());
    aux = dice;
    
    vector<int> A;
    vector<int> B;
    
    bf(0, dice, A, B);
    
    answer = result;
    transform(answer.begin(), answer.end(), answer.begin(), [](int x){ return x+1; });
    
    return answer;
}