[프로그래머스] 카운트 다운

사용 언어: Kotlin

 

문제

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

프로그래머스

 

목표 점수 target이 있을 때, 다트를 최소한으로 던진 경우 중, 싱글이나 불을 최대한 많이 맞춘 경우의 각 횟수를 배열에 담아 return한다.

점수가 target을 초과할 수 없다.

제한사항

1 <= target <= 100,000

풀이

점수 N일 때, 다트를 던진 횟수와 싱글 혹은 불을 맞춘 횟수의 쌍을 f(N) = (a, b)라고 정의할 때,

우선, 점수 N (N <= 60)에 해당하는 최적의 값은 아래와 같다.

f(N) = (1,1) (N <= 20) //싱글
f(N) = (1,1) (N = 50) //불
f(N) = (1,0) (20 < N <= 40, N % 2 = 0) //더블
f(N) = (1,0) (20 < N <= 60, N % 3 = 0) //트리플
f(N) = (2,2) (20 < N < 40) // 이외의 경우. 싱글 2번
f(N) = (2,1) (40 < N < 60) // 싱글 1번 + 더블 or 트리플 1번

각 점수 N을 달성하기 위해선, 이전 회차에서 던진 점수의 최적의 경우 + N을 달성하기 위한 점수의 최적의 경우가 되어야 한다.

예를 들어, 61점을 만들기 위해서는 다음과 같은 경우가 있다.

21(트리플) + 40(더블) = (2,0) // 첫 회차에서 (1,0), 두번째 회차에서 (1,0)
11(싱글) + 50(불) = (2,2) // 첫 회차에서 (1,1), 두번쨰 회차에서 (1,1)

이때, 21+40의 값이 아닌, 11+50의 값인 (2,2)가 최적의 값이라는 것이다.

이런 규칙은 모든 자연수 N에 적용되기 때문에, 아래와 같이 정의한다.

dp[i] = i점을 획득하기 위한 (다트를 던진 최소값, 싱글 / 불을 맞춘 최대값)

f(x) = (1,1) (x <= 20) //싱글
f(x) = (1,1) (x = 50) //불
f(x) = (1,0) (20 < x <= 40, x % 2 = 0) //더블
f(x) = (1,0) (20 < x <= 60, x % 3 = 0) //트리플

dp[0] = (0,0)
dp[i] = max(dp[i-X] + f(x)) // X : f(x)에서 정의된 모든 x

 

 

 

코드

fun solution(target: Int): IntArray {
    val dp = Array(target+1) { Int.MAX_VALUE to Int.MAX_VALUE }
    dp[0] = 0 to 0
    for(i in 1 until dp.size) {
        for(j in 1..20) { // 싱글
            if(i < j) break
            val temp = dp[i-j].first + 1 to dp[i-j].second + 1
            dp[i] = max(temp, dp[i])
        }
        for (j in 22..40 step 2) { // 더블
            if(i < j) break
            val temp = dp[i-j].first + 1 to dp[i-j].second
            dp[i] = max(temp, dp[i])
        }
        for(j in 21..60 step 3) { // 트리플
            if(i < j) break
            val temp = dp[i-j].first + 1 to dp[i-j].second
            dp[i] = max(temp, dp[i])
        }
        if(i < 50) continue // 불
        val temp = dp[i-50].first + 1 to dp[i-50].second + 1
        dp[i] = max(temp, dp[i])
    }
    return intArrayOf(dp.last().first, dp.last().second)
}

fun max(a: Pair<Int, Int>, b: Pair<Int, Int>) 
= if(a.first < b.first) a else if(a.first == b.first && a.second > b.second) a else b