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

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

프로그래머스

 

[문제 요약]

 

1. N 개의 주사위를 2명이서 나누어 가진다 ( 문제 조건에 의하면 N은 2의 배수 )

2. 가져간 주사위를 굴려서 나온 숫자들을 모두 더한다.

3. 모든 경우의 수에서 이길 수 있는 경우, 비기는 경우, 지는 경우를 구한다 했을 때, 가장 승리 경우가 높은 주사위는?

 

 

[아이디어 구상]

일단 문제를 보고 처음으로 생각난건 조합을 하는 거였다. 

그리고 적용할 만한 다른 알고리즘이 있나 고민해 봤는데 딱히 생각나는게 없었다...

 

그래서 완전 탐색으로 풀 수 있는지 시간 복잡도를 고려해봤는데. (최대의 경우 주사위가 10개인 경우 고려)

1. DFS 사용 조합 => 2^10 
2. 5개씩의 주사위라고 쳤을 때, 한 주사위의 6면 중 하나씩 고르는 방법 => 6^5 + 6^5 => 2*6^5
3. 모든 경우의 수 (1) 에서 한면씩 고른다 => 1의 공간 복잡도 * 2의 시간 복잡도 

 

다른 자잘한 부분들은 제외하고, 시간복잡도가 크게 걸릴 것으로 생각나는 경우는 위의 두 경우였는데, 

1. 시간 복잡도 = 1024, 공간 복잡도 = 10C5 -> 252
2. 시간 복잡도 = 2^5 * 3^5 = 7500 (올림, 내림 어림잡아 계산) 
3. 252*7500 = 2,250,000 (252를 300으로 올려서 어림 계산) 

 

대충 2.3백만 정도로 나와서 생각보다 시간이 오래 걸리진 않는단 걸 알 수 있었다. 

그래서 완전 탐색을 사용하기로 결정했다.

 

알고리즘을 풀기 전에 스도코드를 써보고 푸는 식으로 해서 실수를 줄이자고 마음 먹었었는데, 이 정도 길이 되니까 스도코드는 쓸 엄두가 안나서 돌아갈 순서? 정도만 적고 진행을 했다. 

 

1. 주사위를 선택하는 조합을 진행한다.
2. 주사위의 모든 경우의 수는 comb라는 vector에 넣는다. 
3. comb 벡터를 돌아가며 나올 수 있는 수의 합을 구해준다.
    - 이 부분에서 선택한 주사위를 제외한 경우의 수도 함께 구해줘야함. => 1번의 조합에서 1,0으로 마스킹하는 방법 선택
    -  
4. 나온 수를 비교하며 승리수를 따져준다 
    - 문제에 의하면 비기고, 지는 경우는 생각하지 않아도 된다. "승리 경우"만 따져주면 된다.

 

[문제 풀이]

1. 주사위를 선택하는 조합을 진행한다.
2. 주사위의 모든 경우의 수는 comb라는 vector에 넣는다. 
3. comb 벡터를 돌아가며 나올 수 있는 수의 합을 구해준다.
    - 이 부분에서 선택한 주사위를 제외한 경우의 수도 함께 구해줘야함. => 1번의 조합에서 1,0으로 마스킹하는 방법 선택
    -  합의 경우를 모두 구한 후 이기는지 비기는지를 따져줘야 하기 때문에 합을 어딘가에 "저장"해둬야 함. 
4. 나온 수를 비교하며 승리수를 따져준다 
    - 문제에 의하면 비기고, 지는 경우는 생각하지 않아도 된다. "승리 경우"만 따져주면 된다.
    - 빠르게 비교해주기 위해 누적합을 사용했다. 

 

 

1. 주사위를 선택하는 조합을 진행한다. ( combination 함수 )

    - 3번을 생각하면서 조합 시에 1,0 으로 되어있는 팀을 나누는 방법을 사용해야 한다는 것을 알 수 있었다.

    - 종료 조건은 선택한 주사위의 개수가 N/2가 되었을 때 ( 2. 이 땐, 조합을 저장한다 )

    - 주사위의 범위를 넘어갈 때 

 

 

3. comb 벡터를 돌아가며 나올 수 있는 수의 합을 구해준다.
    - 이 부분에서 선택한 주사위를 제외한 경우의 수도 함께 구해줘야함.

    -  합의 경우를 모두 구한 후 이기는지 비기는지를 따져줘야 하기 때문에 합을 어딘가에 "저장"해둬야 함.

 

파라미터 정보는 다음과 같다.

solved(주사위 정보, 조합, 선택완료된 주사위 개수, 합, 0인지 1인지)

 

solved라는 함수로 구해줬는데, 0인 경우 1인 경우 모두 조합을 진행해야해서 동시엔 진행 못하고 flag를 통해서 1인 경우, 0인 경우를 따로 구해줬다. 뭔가 방법이 있을지도?

 

종료 조건은 d==N일때이고 이 경우에는 sol이라는 함수에 더해진 숫자를 모두 저장해 줬다. 

* 문제에 의하면 주사위 한 면의 최대 값은 100이기 때문에 결국 합이 500을 넘을 수 없다 -> sol[502] 배열에 저장.

 

* 문제를 풀면서 이 배열에 저장하는 방법을 선택한 이유가 합을 저장한다고 했을 때, 이기고 지는 경우를 쉽게 하기 위해서 였다. 처음엔 벡터에 저장하고 정렬하는 식을 생각했었는데 앞에 구현한다고 머리가 복잡했다....

그래서 생각난 방법이 누적합이었음.... 둘 다 같은 크기의 배열이기 때문에 상대 배열에서 현재 직전 인덱스의 누적합으로 하면 되겠다는 생각이었다. 

 

 

4. 나온 수를 비교하며 승리수를 따져준다 
    - 문제에 의하면 비기고, 지는 경우는 생각하지 않아도 된다. "승리 경우"만 따져주면 된다.
    - 빠르게 비교해주기 위해 누적합을 사용했다.

 

보면, 답의 경우의 수가 저장되어 있는 sol1과 sol2의 배열을 돌아가면서 

합의 수가 나오는 경우가 있다면, win1, win2 변수에 저장해준다. 

이 때 1의 조합이 이기는 경우 = 0이 지는 경우 * 1의 현재 수 임

288	299	300
9	0	2
5	0	3

 

sol0[288], sol1[288]에선 직전까지 누적합이 들어 있고 299의 합이 나오는 경우가 없기 때문에 그대로 누적합을 진행한다. 

288	299	300
9	9	2
5	5	3

 

300에서는 sol0은 2개, sol1은 3개의 경우가 들어있다. 

그럼 sol0의 수가 300일 때 sol1이 지는 방법은 sol1[299] * sol0[300] 이 되는 것임 ㅇㅇ... 

그걸 sol1도 동일하게 진행하면 된다. 

 

 

구해야 하는게 가장 높은 승리 확률을 가진 주사위 이기 때문에 win_max라는 변수를 따로 두고 비교까지 해주면 된다.... 

 

[전체 풀이 코드]

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<vector<int>> comb;
int sol1[502];
int sol0[502];

int combination(vector<int> v, int i, int n) {
    if (n == N / 2) {
        comb.push_back(v);
        return 0;
    }
    if (i >= N) return 0;

    v[i] = 1;
    combination(v, i + 1, n + 1);
    v[i] = 0;
    combination(v, i + 1, n);

    return 0;
}

void solved(vector<vector<int>>& dice, vector<int>& com, int d, int ans, int flag) {

    if (d == N) {
        if (flag) {
            sol1[ans]++;

        }
        else {
            sol0[ans]++;
        }

        return;
    }

    if (com[d] == flag) {
        for (int i = 0; i < 6; i++) {
            solved(dice, com, d + 1, ans + dice[d][i], flag);
        }
    }
    else {
        solved(dice, com, d + 1, ans, flag);
    }

}

vector<int> solution(vector<vector<int>> dice) {
    N = dice.size();
    vector<int> v(N);
    fill(v.begin(), v.end(), 0);
    v[0] = 1;
    combination(v, 1, 1);

    int ans = 0;
    int flag = 1;
    int win_max = 0;

    vector<int> answer;

    for (int i = 0; i < comb.size(); i++) {
        fill(sol1, sol1 + 502, 0);
        fill(sol0, sol0 + 502, 0);
        solved(dice, comb[i], 0, 0, 1);
        solved(dice, comb[i], 0, 0, 0);
        int win1 = 0;
        int win0 = 0;
        for (int j = 1; j < 502; j++) {
            if (sol1[j]) {
                win1 += sol0[j - 1] * sol1[j];
            }if (sol0[j]) {
                win0 += sol1[j - 1] * sol0[j];
            }
            sol1[j] += sol1[j - 1];
            sol0[j] += sol0[j - 1];
        }
        if (win1 > win0 && win_max < win1) {
            ans = i;
            win_max = win1;
            flag = 1;
        }
        if (win0 > win1 && win_max < win0) {
            ans = i;
            win_max = win0;
            flag = 0;
        }

    }
    for (int i = 0; i < N; i++) {
        if (comb[ans][i] == flag) {
            answer.push_back(i + 1);
        }
    }

    return answer;
}

 

 

 

[고찰 및 추가할 점]

https://tech.kakao.com/2023/12/27/2024-coding-test-winter-internship/

2024 카카오 겨울 인턴십 코딩테스트 문제해설

몰랐는데 카카오에서는 코테 해설을 올려준다. 사실 풀이는 없고 힌트 정도인 듯~~

 

combination은 구현해줬는데, next_permutation으로도 가능할 듯 하다. 

 

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main (){

	// 1부터 6까지 담을 벡터
	vector<int> n;

	// 1부터 6까지 생성
	for(int i=0; i<6; i++){
		n.push_back(i+1);
	}

	// 0과1을 저장 할 벡터 생성
	vector<int> ind;

	// k=4, 4개를 뽑으니까
	int k = 4;

	// k개의 1 추가
	for(int i=0; i<k; i++){
		ind.push_back(1);
	}

	// 2개(6개-2개)의 0 추가
	for(int i=0; i<n.size()-k; i++){
		ind.push_back(0);
	}

	// 정렬
	sort(ind.begin(), ind.end());

	//순열
	do{
		// 출력
		for(int i=0; i<ind.size(); i++){
			if(ind[i] == 1){
				printf("%d ", n[i]);
			}
		}

		printf("\n");

	}while(next_permutation(ind.begin(), ind.end()));

	return 0;

}

 

그리고 풀이 중에 시간 걸리지말라고 기도하면서 푸느라 이것저것 많이 고려해줬는데 그 중 하나가 

 

이 부분이다. 즉, 1을 무조건 포함하는 거다. 

왜냐면, 주사위 중 빠지는 것 없이 선택하기 때문에 

1을 포함한 N/2개, 1을 포함하지 않은 N/2개 두가지 경우로 나눠진다.

 

1을 포함하지 않은 경우는 결국 0으로 표기돼서 뒤에서 다 계산해주기 때문에 저렇게 하면

시간을 9C4로 줄일 수 있고 

그냥 돌리는 것 보다 경우의 수도 줄일 수 있다고 생각했다.

 

추가로 글 쓰면서 생각한건데, 6개 경우 구해주는 것도 1,2,3,4,5,6 여섯개씩 넣어서 순열로도 할 수 있을 것 같다 ㅎㅎ