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

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

프로그래머스

 

 

생각 흐름

• 가장 최악으로 먼저 생각하자. n을 10개로 고정
• A가 주사위를 굴려서 나올 수 있는 합의 경우의 수 7776개
• 10개의 주사위를 고르는 경우의 수, 10c5(252) 중에 절반만 구해도 됨. -> 절반 구하면 나머지 절반은 알아서 자동으로 설정 됨. 
• 절반의 경우에도 이긴 경우 구해야 하므로 *2 해줘야 하므로 지금까지 126*7776*2임.
• 다이스가 이기는 경우만 따지므로 A와 B가 고른 다이스 주사위 모든 합에 대해 정렬 후 lower_bound 적용함.
• 정렬은 O(nlogn)이고 lower_bound는 O(logn)이므로 총 시간 복잡도는 126*(7776+(13*7776)+(13*7776))*2인 거 같다.
• 따라서 시간은 충분하다고 판단 이후 문제 풀이 시작 이후 정답 도출

 

#include <vector>
#include <algorithm>

using namespace std;

int n;
bool checked[11];
vector<vector<int>> globalDice;
int maxWinCount;
vector<int> answer;

void cal(int i, vector<int> diceTmp, int result, vector<int>& diceTmpResult){
    if(i==globalDice.size()/2){
        diceTmpResult.push_back(result);
        return;
    }
    for(int j = 0; j<6; j++){
        cal(i+1, diceTmp, result+globalDice[diceTmp[i]-1][j], diceTmpResult);
    }
}

int combiCount=0;
void combi(int depth, int diceCount){
    if(combiCount==n){
        return;
    }
    if(diceCount==globalDice.size()/2){
        combiCount++;
        vector<int> diceA, diceB;
        
        for(int i = 1; i<=globalDice.size(); i++){
            if(checked[i]){
                diceA.push_back(i);
            }else{
                diceB.push_back(i);
            }
        }
        vector<int> diceACase, diceBCase;
        
        cal(0, diceA, 0, diceACase);
        cal(0, diceB, 0 ,diceBCase);
        
        sort(diceACase.begin(), diceACase.end());
        sort(diceBCase.begin(), diceBCase.end());
        
        int winCount = 0;
        for (int i = 0; i < diceBCase.size(); i++){
            winCount += lower_bound(diceACase.begin(), diceACase.end(), diceBCase[i])-diceACase.begin();
        }

        if (winCount > maxWinCount){
            maxWinCount = winCount;
            answer = diceB;
        }
        
        winCount = 0;
        for (int i = 0; i < diceACase.size(); i++){
            winCount += lower_bound(diceBCase.begin(), diceBCase.end(), diceACase[i])-diceBCase.begin();
        }
        
        if (winCount > maxWinCount){
            maxWinCount = winCount;
            answer = diceA;
        }
        
        return;
    }
    for(int i = depth+1; i<=globalDice.size(); i++){
        checked[i]=true;
        combi(i, diceCount+1);
        checked[i]=false;
    }
}

vector<int> solution(vector<vector<int>> dice) {
    int tmp[5] = {1, 3, 10, 35, 126};
    int diceSize = (int)dice.size();
    n = tmp[diceSize/2-1];
    globalDice = dice;
    combi(0,0);
    
    return answer;
}