[틀림] 프로그래머스 주사위고르기 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;
}

 

* 25.5.10. 2회독

시도1

시키는대로 완전탐색

주사위 절반고르고 (10C5)

전체주사위 탐색하고 (6^10)

150억 -> 시간초과

아이디어 필요

 

풀이

주사위를 절반씩 나눠가지고(10C5), dfs로 합을 탐색후(6^5), 각각 배열을 이용해서 합을 저장해놓는 idea

이후 이분탐색으로 나보다 작은것의 갯수를 빨리 찾을수 있음.

10C5 조합돌리기에는 비트를 사용하면 좋다. (n이 10밖에 안되므로)

아래로 타고 내려가면서 주사위 합을 구하는것에는 dfs를 사용

이분탐색은 자바에 lower_bound가 없으므로 이를구현해줘야 한다.

x=3이고 배열이 [1 4 4 4 ] 인경우, 인덱스 1이 반환 -> 나보다 작은것의 갯수와 같음. == A가 이기는 경우의 수

lower_bound 구현

목표 : x이상인것 구하기

주의사항 : en을 n으로 둬야한다.

ret 초기값을 en으로 둬야한다. // ex: x=4이고 [ 1 1 1 1 1 1 1] 인경우, 끝 인덱스를 리턴해야함.

int lower_bound(ArrayList<Integer> v, int x){
        int st=0;
        int en=v.size(); //불포함
        int ret=en; //한번도 갱신안될때 기본값!! (x보다 다 작은경우 생각)
        while(st<en){
            int mid = (st+en)/2;
            if(v.get(mid) >= x){ //mid가 크다 -> 정렬되있으므로 mid앞쪽에 정답후보
                ret=mid;
                en=mid;
            }
            else{
                // mid가 작다 -> 정렬되있으므로 mid이하는 볼 필요가없음.
                st=mid+1;  
            }
        }
        return ret;
    }

정답코드

import java.util.*;

class Solution {
    static int n;
    static int[][] dice = new int[11][6];
    
    void dfs(int depth, int sum, ArrayList<Integer> v, ArrayList<Integer> arrA){
        if(depth==v.size()){
            arrA.add(sum);
            return;
        }
        
        for(int i=0;i<6;++i){
            dfs(depth+1,sum+dice[v.get(depth)][i],v,arrA);
        }
    }
    
    int lower_bound(ArrayList<Integer> v, int x){
        int st=0;
        int en=v.size(); //불포함
        int ret=en; //한번도 갱신안될때 기본값!! (x보다 다 작은경우 생각)
        while(st<en){
            int mid = (st+en)/2;
            if(v.get(mid) >= x){ //mid가 크다 -> 정렬되있으므로 mid앞쪽에 정답후보
                ret=mid;
                en=mid;
            }
            else{
                // mid가 작다 -> 정렬되있으므로 mid이하는 볼 필요가없음.
                st=mid+1;  
            }
        }
        return ret;
    }
    
    public int[] solution(int[][] _dice) {
        
        // System.out.println(Math.pow(6,10)); //6천만
        // //10C5 = 18*14 = 252
        // System.out.println(Math.log(Math.pow(6,5)));
        // double a = Math.pow(6,5);
        // double b = Math.log(Math.pow(6,5));
        // System.out.println(252*(a+a+a*b*2+b));
        dice=_dice;
        n=dice.length;
        int[] answer = new int[n/2];
        
        int maxW=0;
        
        for(int subset=0;subset<(1<<n)-1;++subset){
            int cnt=0;

            ArrayList<Integer> A = new ArrayList<>();
            ArrayList<Integer> B = new ArrayList<>();
            for(int i=0;i<n;++i){
                if((subset & (1<<i)) >0){
                    cnt++;
                    A.add(i);
                }
                else{
                    B.add(i);
                }
            }
            if(cnt==n/2){
                // System.out.println(A);
                ArrayList<Integer> arrA = new ArrayList<>();
                ArrayList<Integer> arrB = new ArrayList<>();
                dfs(0,0,A,arrA);
                dfs(0,0,B,arrB);
                // System.out.println(arrA);
                // System.out.println(arrB);
                
                Collections.sort(arrA);
                Collections.sort(arrB);
                int winA=0;
                for(int x : arrA){
                    int idx = lower_bound(arrB,x);
                    winA+=idx;
                    // int idx = Collections.binarySearch(arrB, x);
                    // int lb  = (idx >= 0) ? idx : -idx - 1;
                    // winA+=lb;
                }
                if(winA > maxW){
                    System.out.print(winA);
                    System.out.println(A);
                    maxW=winA;
                    for(int i=0;i<A.size();++i){
                        answer[i]=A.get(i)+1;
                    }
                }
            }
        }
        
        // ArrayList<Integer> arrA = new ArrayList<>();
        // arrA.add(0); arrA.add(2); arrA.add(4); arrA.add(4);
        // int q = lower_bound(arrA,3);
        // System.out.println(q);
        return answer;
    }
}