[programmers/js] [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

[PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

https://school.programmers.co.kr/learn/courses/30/lessons/340212?language=javascript

문제 설명

당신은 순서대로 n개의 퍼즐을 제한 시간 내에 풀어야 하는 퍼즐 게임을 하고 있습니다.

당신의 숙련도에 따라 퍼즐을 풀 때 틀리는 횟수가 바뀌게 됩니다. 현재 퍼즐의 난이도를 diff, 현재 퍼즐의 소요 시간을 time_cur, 이전 퍼즐의 소요 시간을 time_prev, 당신의 숙련도를 level이라 하면, 게임은 다음과 같이 진행됩니다.

diff ≤ level이면 퍼즐을 틀리지 않고 time_cur만큼의 시간을 사용하여 해결합니다.
diff > level이면, 퍼즐을 총 diff - level번 틀립니다. 퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다. 이전 퍼즐을 다시 풀 때는 이전 퍼즐의 난이도에 상관없이 틀리지 않습니다. diff - level번 틀린 이후에 다시 퍼즐을 풀면 time_cur만큼의 시간을 사용하여 퍼즐을 해결합니다.

요약하면 밑의 두 경우로 구분됩니다.
1. diffs[i] > level => (diffs[i] - level) * (times[i-1] + times[i]) + times[i]
2. diffs[i] <= level => times[i]

풀이

이중 반복문을 사용하면 시간 초과가 발생
이분 탐색을 사용하면 시간 초과는 해결하지만, 숫자가 커서 에러가 발생합니다.
따라서 BigInt로 변경 후 답을 구해줍니다.

function solution(diffs, times, limit) {
    times = times.map((e) => BigInt(e));
    diffs = diffs.map((e) => BigInt(e));
    
    const calcTime = (level) => {
        let usingTime = 0n;
        
        for (let i = 0; i < diffs.length; i++) {
            if (diffs[i] > level) usingTime += (diffs[i] - level) * (times[i-1] + times[i]) + times[i]
            else usingTime += times[i];
        }
        
        return usingTime;
    }
    
    let left = 1n;
    let right = diffs.reduce((acc, e) => acc < e ? e : acc, 0n);
    
    while (left <= right) {
        const mid = (left + right) / 2n;
        const time = calcTime(mid);
        
        if (time <= limit) right = mid - 1n;
        else left = mid + 1n;
    }
    
    return left;
}