카운트 다운

🔗 문제 링크

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

🎯 다트 점수(target) 만들기 — DP(Top-Down) 풀이 정리

다음은 특정 target 점수를 만들기 위해
싱글, 더블, 트리플, 불(Bull) 등을 던져 가장 적은 횟수로 도달하는 최적값을 찾는 문제를
DP(Top-Down) 방식으로 해결한 방법 정리이다.

🧠 접근 방법

이 문제는 DFS + 메모이제이션(Top-Down DP) 으로 해결할 수 있다.
핵심은 다음과 같다.

1. DP 정의

dp[i] = score == i 일 때 target 점수에 도달하는 최적의 결과 {총 던진 횟수, 싱글/불 횟수}
예: 3000 → 3300 에 5번이 최적이라면 DP에 저장된다.

2. Top-Down 탐색

0점부터 시작해 가능한 모든 점수 연산(싱글, 더블, 트리플, 불)을 재귀적으로 진행하며
각 score마다 최적값을 구해 저장한다.

3. target 초과 시 무효 처리

score > target이면 더 진행할 필요가 없으므로 {INF, INF} 같은 invalid 값을 반환한다.

4. target 도달

score == target이면 {0, 0} 을 반환한다.
(더 던질 필요 없음)

5. 이미 구한 score는 재사용

만약 dp[score]에 값이 있다면 다시 계산하지 않고 바로 리턴한다.

6. 가능한 모든 던지기 방식 탐색

각 점수 i(1~20)에 대해 아래 네 가지를 모두 시도한다.

싱글 → score + i

더블 → score + 2i

트리플 → score + 3i

불(Bull) → score + 50

7. 결과 비교 기준

각 선택의 결과 {총 던진 횟수, 싱글/불 횟수} 중

총 던진 횟수 최소화

총 횟수가 같다면 싱글/불 횟수 최대화

으로 비교하여 최적값을 선택한다.

8. dp에 최종 결과 저장
   ⏱ 시간 복잡도

최대 score는 target까지

각 score마다 61가지 경우
(싱글·더블·트리플 60개 + 불 1개)

O(N × 61)
즉 사실상 O(N).

import java.util.*;

class Solution {
    
    public int target;
    public int[][] dp;
    public final int INF = 100_000_000;
    
    public void swap(int[] b, int[] min) { // min 을 최적의 값으로 갱신해주는 메서드 
       	if (b[0] <= min[0]) { // 더 작거나 같은 경우만
            if (b[0] == min[0]) { // 같으면
                if (min[1] < b[1]) { // (싱글, 불) 을 던진 횟수를 비교하여 현재가 더 많으면 갱신
                    min[0] = b[0];
                    min[1] = b[1];
                }
            } else { // 아예 던진 횟수가 적다면 바로 현재의 값으로 갱신
                min[0] = b[0];
                min[1] = b[1];
            }
        }
    }
    
    public int[] dfs(int score) {
        if (target < score) { // target 을 넘어버린 경우
            return new int[] {INF, INF};
        }
        
        if (score == target) { // 잘 도착한 경우
            return new int[] {0, 0};
       	}
        
        if (dp[score][0] != -1) { // 이미 최적해를 구한 경우
            return dp[score];
        }
         
        int[] min = new int[] {INF, INF}; // 초기 min 값은 invalid 한 값으로
        
        for (int i = 1; i <= 20; i++) { // 싱글
            int[] a = dfs(score + (i * 1));
            int[] b = new int[] {a[0] + 1, a[1] + 1}; // 던진 횟수, (싱글, 불) 횟수 + 1
            swap(b, min); // 최적의 값을 min 값에 대입
        }
        
        for (int i = 1; i <= 20; i++) { // 더블
            int[] a = dfs(score + (i * 2));
            int[] b = new int[] {a[0] + 1, a[1]}; // 던진 횟수만 + 1
            swap(b, min); // 최적의 값을 min 값에 대입
        }
        
        for (int i = 1; i <= 20; i++) { // 트리플
            int[] a = dfs(score + (i * 3));
            int[] b = new int[] {a[0] + 1, a[1]}; // 던진 횟수만 + 1
            swap(b, min); // 최적의 값을 min 값에 대입
        }
        
        int[] a = dfs(score + 50); // 불
        int[] b = new int[] {a[0] + 1, a[1] + 1}; // 던진 횟수 + 1, (싱글, 불) 횟수 + 1
        swap(b, min); // 최적의 값을 min 값에 대입
        dp[score] = min; // dp[score] 를 최적의 값으로 갱신
        
        return dp[score];
    }
    
    public int[] solution(int target) {
        this.target = target;
        dp = new int[target + 1][2]; // 20 만
        
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], -1); // 방문처리를 하기 위해 초기값으로 세팅
        }
        
        return dfs(0); // 0 -> target 을 만들기 위해 0점으로 시작
    }
}