주사위 고르기

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

프로그래머스

주사위 갯수 N개가 있을 때, 두 명의 플레이어가 절반의 주사위를 선택한 다음 자신이 선택한 주사위들을 굴러서 나온 합이 상대방이 굴렀을 때 나온 주사위 합보다 크다면 이기는 게임이다. 

주사위는 육면이므로 한 명의 플레이어가 주사위들을 굴렀을 때 나오는 경우의 수는 6**(N/2) 이다. 

상대방이 낼 수 있는 경우의 수도 6**(N/2)이므로 각각의 플레이어가 주사위 절반들을 골랐을 때 나올 수 있는 경우의 수는 2* 6**(n/2)이다. 여기에 주사위 절반을 선택하는 경우의 수는 nC(n/2) 이므로 결국 총 경우의 수는 (nC(n/2))*(2* 6**(n/2) ) 이다.

주사위의 최대 갯수는 10개 이므로 최대 3백만 정도의 경우의 수가 나옴.

따라서 모든 경우를 탐색한다고 해도 시간 초과가 발생할 확률은 낮다고 판단함.

따라서 플레이어들이 주사위를 고르는 조합들을 우선적으로 찾아내고 해당 주사위 조합에서 나올 수 있는 모든 합들을 객체에 기록해뒀다.

const n = dices.length;
const combinations = [];
const getCombi = (arr, idx) => {
    if (arr.length === n / 2) {
        combinations.push(arr);
        return;
    }
    for (let i = idx + 1; i < n; i++) {
        getCombi([...arr, i], i);
    }
};
getCombi([], -1);

const recordSum = {};
for (const combi of combinations) {
    const key = combi.join('-');
    const sum = [];

    const getSums = (s, diceRow) => {
        if (diceRow >= n / 2) {
            sum.push(s);
            return;
        }

        for (let col = 0; col < 6; col++) {
            const diceNum = combi[diceRow];
            const num = dices[diceNum][col];
            getSums(s + num, diceRow + 1);
        }
    };
    getSums(0, 0);
    recordSum[key] = sum.sort((a, b) => a - b);
}

위와 같이 주사위를 선택한 뒤 나올 수 있는 합의 배열을 구해둔 뒤, 주사위 조합에서 다른 조합의 합과 비교해가며 이길 수 있는 경우의 수를 구한다. 비교해가며 이길 수 있는 경우의 수는 이분 탐색을 활용했다. 소스 값이 비교할려는 배열에 들어 갈 수 있는 인덱스 자체가 이 수로 이길 수 있는 경우의 수를 뜻하기 때문이다. 떄문에 위 코드에서 sum.sort를 실행시킨 것

const keys = Object.keys(recordSum);

const binarySearch = (src, targetArr) => {
    let start = 0;
    let end = targetArr.length - 1;

    while (start <= end) {
        const mid = Math.floor((start + end) / 2);

        if (targetArr[mid] < src) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return start;
};

const dp = Array.from({ length: keys.length }, () =>
    Array.from({ length: keys.length }, () => 0)
);

for (let i = 0; i < keys.length; i++) {
    const sums = recordSum[keys[i]];
    const k = keys[i].split('-');

    for (let j = 0; j < keys.length; j++) {
        const kk = keys[j].split('-');
        if (kk.some((v) => k.includes(v))) continue;

        let s = 0;

        for (const num of sums) {
            const idx = binarySearch(num, recordSum[keys[j]]);
            s += idx; //s는 인덱스임. 경우의 수를 다시 생각해보기
        }
        dp[i][j] = s;
    }
}

이때 주의할 점은 현재 주사위 조합에서 다른 주사위 조합을 비교할때 겹치는 주사위가 없어야 하므로 kk.some을 통해 이를 체크해야한다는 것이다.

이제 위의 결과를 통해 dp가 도출될 것이고 각 행의 합이 제일 큰 주사위 조합이 정답으로 출력되면 된다.

이때 주사위 키는 인덱스로 처리되어 있기에 return시에 +1씩 해줘야 한다.

let maxLen = 0;
let keyIdx = -1;
for (let i = 0; i < keys.length; i++) {
    const s = dp[i].reduce((a, c) => a + c, 0);
    if (s > maxLen) {
        maxLen = s;
        keyIdx = i;
    }
}

return keys[keyIdx].split('-').map((v) => Number(v) + 1);