[lv3] 카운트 다운

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

 

조금 어려웠던 DP문제다.

 

접근법

 

[싱글 & 불]에 대해 :

- 더 적은 시행 횟수(dp[i][0])나, 시행 횟수를 늘리지 않고 더 높은 점수(dp[i][1])인 경우를 기록한다.

 

[더블 & 트리플]에 대해 :

- 더 적은 시행횟수(dp[i][0])인 경우를 기록한다.

 

[더블 & 트리플] 탐색은 점수를 늘리지 않으므로, 점수를 비교할 필요는 없다.

- i번째 dp를 탐색 중이라면, 이전의 점수(자연수 n에 대해, dp[i-n][1])는 항상 최적임이 보장된다.

=> i-n번째 [싱글 & 불]의 탐색에서 이미 갱신했음

---

 

생각해본 다른 풀이

- 시간초과 요인은 target(10만)이며, 다트를 던지는 경우의 수(60)는 많지 않아서 가능할 듯 하다.

 

1. 이분탐색 : 던진 횟수를 mid로 놓고, 1 <= target <= 10만에 대해 min(mid)를 구한다.

=> 시간 복잡도를 위해, "현재 mid로 target을 달성할 수 있는지" 만 판별한다.

 

2. min(mid)에 대해서만 한 번 더 탐색하며, max(midVal : 싱글 + 불)을 구한다.

 

class Solution {
    static int[][] dp;
    static int MAX = 100001, target;

    public int[] solution(int target) {
        this.target = target;
        dp = new int[target + 1][2];
        initDP();

		// val : 던진 다트 수, score : (싱글 + 불) 횟수
        for(int i=1; i<=target; i++) {
            for(int j=1; j<=20; j++) {

                if(i - 50 >= 0) {
                    // 불 : 더 적은 val || val을 늘리지 않고 더 높은 score
                    if(dp[i-50][0] + 1 < dp[i][0] ||
                        (dp[i-50][0] < dp[i][0] && dp[i-50][1] >= dp[i][1])) {
                        dp[i][0] = dp[i-50][0] + 1;
                        dp[i][1] = dp[i-50][1] + 1;
                    }
                }

                if(i - j >= 0) {
                    // 싱글 : 더 적은 val || val을 늘리지 않고 더 높은 score
                    if(dp[i-j][0] + 1 < dp[i][0] ||
                        (dp[i-j][0] < dp[i][0] && dp[i-j][1] >= dp[i][1])) {
                        dp[i][0] = dp[i-j][0] + 1;
                        dp[i][1] = dp[i-j][1] + 1;
                    }
                }

                int d = j * 2;

                if(i - d >= 0) {
                    // 더블 : 더 적은 val
                    if(dp[i-d][0] + 1 < dp[i][0]) {
                        dp[i][0] = dp[i-d][0] + 1;
                        dp[i][1] = dp[i-d][1];
                    }
                }

                int t = j * 3;

                if(i - t >= 0) {
                    // 트리플 : 더 적은 val
                    if(dp[i-t][0] + 1 < dp[i][0]) {
                        dp[i][0] = dp[i-t][0] + 1;
                        dp[i][1] = dp[i-t][1];
                    }
                }
            }
        }

        return new int[]{dp[target][0], dp[target][1]};
    }

    static void initDP() {
        for(int i=1; i<=target; i++)
            dp[i][0] = MAX;
    }
}