카운트 다운 (javascript)

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

프로그래머스

 

풀이 

• dp를 이용해서 각 인덱스에는 점수 별로 얻을 수 있는 [최소한의 방법 수, '볼'+'싱글' 횟수] 을 지정해줌
• 50점 배수는 불을 맞춰서 점수를 획득하는 것이 최소한이니 반복문을 이용해서 50점마다 먼저 값을 넣어줌
• 1~60 점 구간에는 다트를 한번이라도 던졌을 때 얻을 수 있는 점수들이 있음
  • 1~20 싱글 => dp[1~20] = [1,1]    <- (한번에 얻을 수 있고, 싱글이니 1 )
  • 20~40 더블 -> 싱글의 2배수인 인덱스들이 존재함 (22,24,26,.....,40) => 해당하는 인덱스에는 [ 1, 0 ] 
  • 40~60 트리플 -> 싱글의 3배수인 인덱스들이 존재함 (42, 45, 48 ,...,60) => 해당 인덱스에는 [1,0] *50은 불로 맞췄으니 거기는 [1,1]로 유지
• 위에서 구한 최소한의 방법을 통해 반복문을 통해 23부터 target까지의 dp들을 구해서 dp[target]을 리턴해줌
  • (23부터 하는 이유는 1부터 22까지는 싱글과 더블,트리플을 통해 이미 구했으므로) 
  •  

function solution(target) {
    const MAX = Number.MAX_SAFE_INTEGER;
    const dp = Array.from({ length: 100_002 }, () => [MAX, 0]);
    let cnt = 50;
    let n = 1;
    while (cnt <= 100_002) {
        dp[cnt] = [n, n++];
        cnt += 50;
    }

    for (let i = 1; i < 4; i++) {
        for (let j = 1; j < 21; j++) {
            const value = i * j;
            if (dp[value][0] === MAX) {
                const cnt = i === 1 ? 1 : 0;
                dp[value] = [1, cnt];
            }
        }
        }

    for (let cur = 23; cur <= target; cur++) {
        for (let mul = 1; mul < 4; mul++) {
            for (let score = 1; score < 21; score++) {
                const totalScore = mul * score;
                if (totalScore > cur) break;
                const restScore = cur - totalScore;
                if (dp[totalScore][0] + dp[restScore][0] > dp[cur][0]) continue;
                else if (dp[cur][0] === dp[totalScore][0] + dp[restScore][0])
                    dp[cur][1] = Math.max(
                        dp[cur][1],
                        dp[totalScore][1] + dp[restScore][1]
                    );
                else
                    dp[cur] = [
                        dp[totalScore][0] + dp[restScore][0],
                        dp[totalScore][1] + dp[restScore][1],
                    ];
            }
        }
    }

    return dp[target];
}

console.log(solution(68));