[프로그래머스] 주사위 굴리기 - 2024 카카오 겨울 인턴십

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

이번에는 주사위 굴리기 문제입니다. 주사위를 던져 나올 수 있는 경우의 수를 전부 고려해야 하는 완전탐색 문제입니다.

---

주사위 굴리기

2 이상 10 이하인 짝수 N개의 주사위를 절반씩 나누어 가져 주사위를 던집니다.

각 주사위의 눈은 1 이상 100 이하입니다.

승부는 주사위를 던져 나온 눈의 합계의 비교를 통해 이루어집니다.

A는 승률이 최대가 되는 주사위 조합을 알고 싶습니다.

단계 요약

1. N개의 주사위 중 N/2개를 선택하는 모든 조합을 구합니다.
2. 단계 1에서 만들어진 조합에 대하여 다음의 과정을 반복합니다.
   1. 조합별로 주사위를 굴렸을 때 얻을 수 있는 결과를 저장합니다.
   2. A로 시뮬레이션한 모든 n에 대하여 B로 시뮬레이션한 결과 중 n보다 작은 수의 숫자를 모두 더하여 승리 횟수를 계산합니다.
   3. 최대 승리 횟수와 현재 조합의 승리 횟수를 비교하여 최대 승리 횟수 및 최대로 승리했을 때의 조합 인덱스를 업데이트합니다.
3. combination[최대 승리 인덱스]를 반환합니다.

---

1. 주사위 조합 생성

N개의 주사위 중 N/2개를 선택하는 조합을 생성합니다. 이것을 A가 가지는 주사위의 조합이라고 했을 때, B가 가지는 주사위의 조합은 자연스럽게 전체 N개의 주사위 중에서 A가 선택한 N/2개의 주사위를 제외하는 방식으로 얻을 수 있을 것입니다.

파이썬의 경우 permutation, combination과 같은 순열·조합 라이브러리가 있어 쉽게 구할 수 있지만 자바스크립트는 직접 탐색을 통하여 조합을 구해야 합니다. 이 부분이 아직 미숙하시다면... 이 문제를 한 번 보시는 것을 추천드립니다.

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

조합 생성 코드

const combination = [];
const tmp = [];
const dfs = (N, prev = 0) => {
    if (tmp.length === N/2){
        combination.push([...tmp]);
        return;
    }
    for (let i = prev + 1; i <= N; i++){
        tmp.push(i);
        dfs(N, i);
        tmp.pop();
    }
}
dfs(N);

코드를 일부 수정하면 N/2개의 요소를 확보할 수 없는 경우에 더이상 재귀 호출이 되지 않도록 할 수 있겠지만 주어지는 N이 크지 않으니 일단은 넘기겠습니다.

N이 4라면, combination 배열은 아래와 같을 것입니다.

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

각 조합의 요소들이 dice 인덱싱에 사용될 것을 고려한다면 처음부터 범위를 1 이상 N 이하가 아닌 0 이상 N-1 이하로 조정하여 배열을 생성할 수도 있습니다.

---

2. 최대 승리 횟수 찾기(반복문)

조합별 시뮬레이션

이 부분도 주사위 조합 생성과 유사합니다. A와 B 각각 시뮬레이션합니다.

A, B를 시뮬레이션한 결과의 개수는 각각 6^(N/2)이 될 것입니다.

시뮬레이션은 각 조합이 가지는 주사위 번호로 dice를 인덱싱하여 크기 6의 점수 배열을 가져와 조합하는 방식으로 진행합니다. 주사위 배열에 접근할 때 주사위 번호 - 1로 인덱싱해야 함에 주의합시다.

주사위 던지기 코드

const simulateDices = (dices) => {
    const result = [];
    const LEN = dices.length;
    const roll = (count = 0, sum = 0) => {
        if (count === LEN){
            result.push(sum);
            return;
        }
        const currentDice = dice[dices[count] - 1];
        for (let i = 0; i < 6; i++){
            roll(count + 1, sum + currentDice[i]);
        }
    }
    roll();
    return result;
}

count는 주사위를 던진 횟수를 세는 동시에 조합에서 현재 던져야 할 주사위를 가져오는 인덱스로 활용됩니다.

6^(LEN) 개수 만큼의 결과를 result에 저장하여 반환합니다.

 

승리 횟수 계산

저는 B를 시뮬레이션한 결과만 오름차순으로 정렬한 후, 이진탐색을 활용하여 A를 시뮬레이션한 모든 결과에 대하여 주어진 수보다 작으면서 가장 큰 인덱스를 찾아 값을 누적하는 방식으로 승리 횟수를 계산하였습니다.

이진 탐색 및 승리 횟수 누적 코드

const binarySearch = (arr, target) => {
    let left = 0;
    let right = arr.length;
    let result = -1;
    while (left <= right){
        let mid = Math.floor((left + right)/2);
        if (arr[mid] < target){
            left = mid + 1;
            result = mid;
        } else {
            right = mid - 1;
        }
    }
    return result + 1;
}

result는 target보다 작은 수가 가질 수 있는 가장 큰 인덱스가 될 것입니다. 이 값은 실제 개수 보다 1 작습니다.

result는 초기에 -1로 설정하고, 결과를 반환할 때 result + 1을 반환함으로써 target보다 작은 요소의 개수와 일치할 수 있도록 조정합니다.

const countWins = (resultA, resultB) => {
    resultB.sort((a, b) => a - b);
    let count = 0;
    for (let num of resultA){
        count += binarySearch(resultB, num);
    }
    return count;
}

B를 시뮬레이션한 결과만 정렬한 뒤, 이진 탐색을 활용하여 승리 횟수를 누적하여 반환합니다.

최대 승리 횟수와 비교

반복문의 외부 스코프에서 최대 승리 횟수 및 그 때의 조합 인덱스를 관리합니다.

각 단계가 끝날 때마다 승리 횟수를 비교해서 업데이트하면 모든 조합에 대한 반복이 종료된 이후에는 전체 조합 중에서 최적의 조합이 남게 됩니다.

---

3. 결과 반환

최종적으로 남은 인덱스를 통하여 결과를 반환합니다.

---

덧

이진 탐색 대신 누적합을 적용해 보았습니다.

[프로그래머스] 주사위 굴리기 리팩토링 - 누적합 적용해 보기

---

공식 문제해설

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

---

같은 시험의 다른 문제

[프로그래머스] 산 모양 타일링 - 2024 카카오 겨울 인턴십