-
카운트 다운 (javascript)코딩 테스트/프로그래머스 2024. 5. 14. 17:02
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));
'코딩 테스트 > 프로그래머스' 카테고리의 다른 글
스타 수열 (Javascript) (0) 2024.05.17 카드 짝 맞추기 (자바스크립트) (0) 2024.05.15 뒤에 있는 큰수 찾기 (자바스크립트) (1) 2024.04.25 셔틀버스 (파이썬) (1) 2023.10.09 연속 펄스 부분 수열의 합 (0) 2023.10.06