주사위 고르기

개인적으로 푸는데 공장히 오랜 시간이 걸린 문제였다. 진짜 시험때는 보자마자 너무 어려웠어서 도전할 엄두도 안났었는데 그때의 긴장감 + 2번 문제를 못풀었던 불안감을 생각하면 지금 돌아가도 아마 못풀었을거다.

이 문제는 주사위를 n/2 개 만큼 가져갔을때 어떤 주사위가 가장 승률이 높은지 찾아야 하는 문제다.

아마 내가 오랜 시간동안 가장 많이 헷갈린 부분은... 어떤 주사위를 찾아갈지 조합적으로 구한다 해도 어떤 상대방 하고 대전해야 할지를 찾는게 가장 의문 이었다.

내가 1,2 번 주사위 가져가면 난 3,4 번 주사위의 조합과 싸워야한다. 근데 이걸 어떻게 찾지?? 했는데 그냥 정답은 간단했다.

모든 조합을 찾은 다음에 가장 왼쪽과 가장 오른쪽에 위치한 조합끼리 대결하면 됐다. backtracking 특성상 stack 이 쌓이면서 계산이 끝날때는 가장 왼쪽과 오른족이 서로의 대전 상대이기 때문이다.

이후에 얻은 조합을 기반으로 모든 주사위의 숫자 조합을 구하는 방법은 letter combination of a phone number 문제가 생각났다. 다중으로 for 룹을 사용하지 않고 backtracking 으로 구하기 위해서는 다중 vector에 index를 하나씩 늘려가서 탐색을 해야 했다.

이후에 서로 비교를 해야하는대 이때는 binary search 를 사용해서 문제를 풀어줬다.

lower_bound() 와 upper_bound() 의 차이점을 한번 다시 학습하니 이해하기 좋았다.

lower_bound() -> 내가 찾고자 하는 target 과 matching 이 될경우 가장 첫번째로 발견한 index를 리턴. 하지만 target 이 없을 경우 target 보다 큰 숫자가 위치한 index를 리턴.

upper_bound() -> 내가 찾고자 하는 target 보다 큰 숫자가 위치한 index를 리턴. target 과 같은 숫자가 있다 해도 더 큰 숫자를 찾아서 준다.

둘 다 공통점으로 찾고자 하는 숫자가 아예 없으면은 한단계 더 높은 index 숫자를 준다. 이때 리턴된 값에서 -1을 해줘서 내가 이길 수 있는 조합의 수 만큼 winRate 를 업데이트 해주고 답을 구했다.

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

void dfs(int N, int target, vector<int>& container, vector<vector<int>>& combinations, int index){
    if(container.size() >= target){
        combinations.push_back(container);
        return; 
    }
    
    for(int i = index; i < N; i++){
        container.push_back(i+1); 
        dfs(N, target, container, combinations, i + 1); 
        container.pop_back(); 
    }
}

void findSum(vector<int>& v, vector<int>& tmp, int& currentSum, vector<vector<int>>& dice, int index){
    if(index >= v.size()){
        tmp.push_back(currentSum);
        return; 
    }
    
    for(int i = 0; i < dice[v[index]-1].size(); i++){
        currentSum += dice[v[index]-1][i];
        findSum(v,tmp,currentSum,dice,index+1); 
        currentSum -= dice[v[index]-1][i]; 
    }
}

vector<int> solution(vector<vector<int>> dice) {
    vector<int> answer = {0,0}; 
    vector<vector<int>> combinations; 
    vector<int> container; 
    int N = dice.size();
    int target = dice.size() / 2; 
    dfs(N,target,container,combinations, 0); 
    int start = 0, end = combinations.size()-1; 
    int curr_maxRate = 0; 
    
    while(start < end){
        int currentSum1 = 0, currentSum2 = 0; 
        vector<int> tmp1, tmp2; 
        
        findSum(combinations[start],tmp1,currentSum1,dice,0); 
        findSum(combinations[end],tmp2,currentSum2,dice,0); 
        
        sort(tmp1.begin(),tmp1.end());
        sort(tmp2.begin(),tmp2.end()); 
        
        int winRate1 = 0, winRate2 = 0; 
        for(int n : tmp1){
            int win = lower_bound(tmp2.begin(), tmp2.end(), n) - tmp2.begin(); 
            if(win - 1 > 0) winRate1 += win; 
        }
        for(int n : tmp2){
            int win = lower_bound(tmp1.begin(), tmp1.end(), n) - tmp1.begin(); 
            if(win - 1 > 0) winRate2 += win; 
        }
        
        
        
        //여기서는 아마 서로 비교하는 계산 로직? 
        if(winRate1 > winRate2){
            if(winRate1 > curr_maxRate){
                curr_maxRate = winRate1; 
                answer = combinations[start];
            }
        } else if(winRate2 > winRate1){
            if(winRate2 > curr_maxRate){
                curr_maxRate = winRate2; 
                answer = combinations[end];
            }
        }
         
        tmp1.clear();
        tmp2.clear(); 
        start++;
        end--; 
    }
    return answer;
}