프로그래머스 주사위고르기 c++ // 빡구현, 완탐, dp, 이분탐색, 발상 아이디어

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

프로그래머스

 

1. 의사코드 고민

완탐? : 10C5 * 6^5 * 10C5 * 6^5 -> 시간초과

상태기반 dp? : (A가고른주사위 bit, B가고른주사위 bit) : 그떄 A의 승수

 같은 상태가 중복되지 않는다... and 매 상태마다 6^5 * 6^5 -> 완탐이나 마찬가지임

 

* dp아이디어 : 메모리, 자료구조(배열)을 이용해 시간복잡도를 줄이자.

각 경우마다 주사위의 합들을 arrA, arrB에  각각 따로 수행 , 저장

복잡도 : //dp : a따로( 10C5 * 6^5 ==1,959,552), b따로계산(1,959,552) / 이후 정렬후 이분탐색 6^5 lg 6^5+ lg 6^5

 

2. 의사코드

0. B의 idx를 찾는방법 : set을 써서, A의 idx를 지우는 방식으로 구현했다.

더좋은방법이 있을까..? n이 10밖에 안되서 ㄱㅊ을듯 하다.

 

1. go함수 :  주사위 idx의 조합을 뽑아 a,b에 저장한다.

2. dfs함수 : 그 조합을가지고 한경우에 대한 주사위의 합을 구한다.

a[depth]에는 A 주사위의 idx가 저장되어있다.

 

주사위 총4개, a에서2개 뽑은경우

2.1. depth를 idx로 사용하고, 해당 depth마다 주사위를택하는 0~5의 자식을 둔다.

2.2. 끝에도달시, sum1을 arrA에 넣는다. sum2를 arrB에 넣는다.

void dfs(vector<int>& a, vector<int>& b, int depth, int sum1,int sum2){
    if(depth==a.size()){
        arrA.push_back(sum1);
        arrB.push_back(sum2);
        return ;
    }
    
    for(int i=0;i<6;++i){
        dfs(a,b,depth+1,sum1+dice[a[depth]][i],sum2+dice[b[depth]][i]);
    }   
}

 

3. go2함수 : 얻어진 arrA, arrB를 이분탐색한다.

*lower_bound : 이상인 첫 idx 반환

a : 5

b: 1 1 1 5 일때,

5의 idx인 3을 반환한다.

관찰결과 idx의 값이 5보다 작은 원소의 갯수이다. == A가 이기는 경우의수

이를 모든 A의 원소에대해 수행한다.

※ 이분탐색대상인 B 는 sort후 사용할것 주의!

 

4. 기존의 max값과 비교해 그게 더크다면, 정답갱신

0-idx를 1-idx로 바꿔야 함에 주의

 

3. 전체코드

#include <bits/stdc++.h>

using namespace std;
int n,arr[11],vis[11],mx;
unordered_set<int> s;
vector<vector<int>> dice;
vector<int> arrA,arrB;
vector<int> answer;

//a의 각원소에대해
//b보다 큰 갯수 == A의 승리갯수
int go2(vector<int>& a, vector<int>& b){
    int ret=0;
    sort(b.begin(),b.end()); //이분탐색은 정렬후 사용!
    for(auto i : a){
        int idx= lower_bound(b.begin(),b.end(),i)-b.begin();
        ret+=idx;
    }
    return ret;
}

//dp : 메모리를 이용해서 시간복잡도 줄이기!
//완탐 : 10C5 * 6^5(1,959,552) * 10C5 * 6^5 -> 시초
//dp : a따로(1,959,552), b따로계산(1,959,552) / 이후 정렬후 이분탐색 6^5 lg 6^5+ lg 6^5
//a,b의 idx를 가지고 합배열만들기
void dfs(vector<int>& a, vector<int>& b, int depth, int sum1,int sum2){
    if(depth==a.size()){
        arrA.push_back(sum1);
        arrB.push_back(sum2);
        return ;
    }
    
    for(int i=0;i<6;++i){
        dfs(a,b,depth+1,sum1+dice[a[depth]][i],sum2+dice[b[depth]][i]);
    }   
}

//현재까지 k 개뽑음
void go(int k){
    if(k==n/2){
        vector<int> a,b; //a,b가 고른 주사위의 인덱스
        for(int i=0;i<n;++i) s.insert(i);
        for(int i=0;i<n/2;++i){
            a.push_back(arr[i]);
            s.erase(arr[i]);
            //cout<<arr[i]<<" ";
        }
        for(auto i : s){
            b.push_back(i);
        }
        // cout<<"a: "; for(auto i : a) cout<<i<<" "; cout<<"\n";
        // cout<<"b: "; for(auto i : b) cout<<i<<" ";
        // cout<<"------------------\n";
        
        arrA.clear();
        arrB.clear();
        dfs(a,b,0,0,0);
        
        //이분탐색
        int cnt = go2(arrA,arrB);
        if(cnt>=mx){ //a의 승률이 큰경우 발견
            mx=cnt;
            answer.clear();
            for(int i : a){
                answer.push_back(i+1); //1-idx로 만듬
            }
        }
        
        
        return;
    }
    
    
    int st=0;
    if(k!=0) st=arr[k-1];
    for(int i=st;i<n;++i){
        if(vis[i]) continue;
        vis[i]=1;
        arr[k]=i;
        go(k+1);
        vis[i]=0;
    }
}
vector<int> solution(vector<vector<int>> _dice) {

    dice=_dice;
    n=dice.size();
    for(int i=0;i<n;++i) s.insert(i);
    go(0);
    return answer;
}