[JS] 카운트 다운

문제 자체는 dp를 활용해서 해결할만한 문제였다.

 

우선 다트는 1~20까지 점수가 있는 판이란 점을 생각하자.

 

dp를 만드는데 [Infinity,0]으로 각 칸을

 

 

dp[n] 이라면 dp[n][0]은 n이라는 점수를 만들기 위해 필요한 다트의 횟수, dp[n][1]은 싱글이나 불을 던진 횟수를 저장하면 될 것이라고 생각했다. 

 

이런방식으로 dp를 구성하면 n이라는 점수를 만들기 위해서 이전 dp에서 2개만 합하면 된다!

 

또한 n이 점수이므로 dp[n]을 만들기 위해 dp[i]를 사용했다면 자연스럽게 더해줄 점수는 dp[n-i]가 된다.

 

 

 

이렇게 dp들을 검사하며

 

1. 다트를 던지는 횟수가 적은경우

2. 다트를 던지는 횟수가 같다면 싱글이나 불 다트를 던진 횟수가 많은경우

 

위 두 조건중 하나에 충족하면 dp를 업데이트해주면된다.

 

 

 

 

그런데,, 시간초과가 발생했다 ㅠㅠ

 

 

 

해당 부분을 고민하다가 힌트를 약간 얻었다. 일정점수 이상(250점) 이상부터는 무조건 60점을 우선 맞춰놓고 그 이하에서 계산하는게 우선이라는 점이다. 따라서 넉넉하게 310개의 dp공간을 두고, 250점 이상이라면 우선 60점을 맞춰놓고 생각하게 하면 dp의 크기를 300여개로 제한한 상태에서 문제를 해결할 수 있다.

 

 

function solution(target) {
    let ret = 0
    
    if (target > 310){
        target -= 250
        ret += ~~(target/60)
        target %=60
        target += 250
    }
    
    
    const dp = [...Array(311)].map(v => [Infinity,0])
    
    for (let i = 1 ; i <= 20; i++){
        dp[i*2] = [1,0]
        dp[i*3] = [1,0] 
    }
    for (let i = 1 ; i <= 20; i++){
        dp[i] = [1,1]
    }
    dp[50] = [1,1]
    
    for (let i = 21 ; i < dp.length ; i++){
        for (let j = 1 ; j < i ; j++){
            const cnt = dp[j][0]+dp[i-j][0]
            const sbCnt = dp[j][1]+dp[i-j][1]
            if (dp[i][0]>cnt){
                dp[i] = [cnt,sbCnt]
            } else if (dp[i][0]===cnt && dp[i][1]<sbCnt){
                dp[i] = [cnt,sbCnt]
            }
        }
    }
    
    
    
    dp[target][0] += ret
    return dp[target]
}