카운트 다운 (Java)

🎯 프로그래머스 - 카운트 다운 문제 풀이 🚀

📌 프로그래머스 카운트 다운 문제

---

📌 문제 설명

🎯 다트 게임에서 목표 점수(Target)를 최소한의 다트 횟수로 맞추는 문제
✔️ 다트 점수 획득 방식

• 불(Bull) → 50점
• 싱글(Single) → 1~20점
• 더블(Double) → 2~40점
• 트리플(Triple) → 3~60점
  ✔ 목표
• 최소한의 다트 횟수로 목표 점수 도달
• 같은 다트 횟수라면 싱글 or 불을 더 많이 사용한 경우를 선택

✅ 출력 → [최소한의 다트 횟수, 싱글 or 불을 맞춘 최대 개수]

---

💡 접근 방식

🔹 1️⃣ 완전 탐색 (DFS) → 비효율적

• 모든 경우의 수를 탐색하는 DFS 사용
• 각 다트 점수(불, 싱글, 더블, 트리플)로 모든 경우를 탐색
• 시간 복잡도: O(4^target) (최악의 경우 2^2000) → 시간 초과 예상 🚨

---

🔹 2️⃣ BFS (최단 거리 탐색) → 비효율적

• BFS로 목표 점수까지 가는 최소한의 횟수 탐색
• 하지만 노드가 너무 많아지면 연산량이 커짐
• 경우의 수가 많아져서 최적화 부족 → 시간 초과 가능성 큼 🚨

---

🔹 3️⃣ DP (Bottom-Up) → 최적화된 해결 방법

💡 점화식 설계 → dp[i] = i 점수를 만드는 최소한의 다트 개수
1. dp[i][0] → i 점수를 맞추는 최소한의 다트 횟수
2. dp[i][1] → 최소한의 다트로 i 점수를 만들 때 싱글/불의 개수
3. 점화식

• dp[i] = min(dp[i-던질 수 있는 점수] + 1)
• 만약 싱글/불을 던졌다면, dp[i][1] = max(dp[i][1], dp[i-던질 점수][1] + 1)

---

📝 코드 구현

import java.util.*;

class Solution {
    int[][] dp;
    public int[] solution(int target) {
        dp = new int[target + 1][2];
        
        // 최소 다트 횟수를 구해야 하므로 초기값을 MAX_VALUE로 설정
        for (int i = 0; i <= target; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        
        dp[0][0] = 0; // 0점 만들기 위해 필요한 다트 횟수는 0
        
        for (int i = 1; i <= target; i++) {
            // 🔹 불(Bull) 처리 (50점)
            if (i - 50 >= 0) {
                if (dp[i][0] > dp[i - 50][0] + 1) {
                    dp[i][0] = dp[i - 50][0] + 1;
                    dp[i][1] = dp[i - 50][1] + 1; // 불을 맞췄으므로 +1
                } else if (dp[i][0] == dp[i - 50][0] + 1) {
                    dp[i][1] = Math.max(dp[i][1], dp[i - 50][1] + 1);
                }
            }

            for (int j = 1; j <= 20; j++) {
                // 🔹 트리플 (3배)
                if (i - j * 3 >= 0) {
                    if (dp[i][0] > dp[i - j * 3][0] + 1) {
                        dp[i][0] = dp[i - j * 3][0] + 1;
                        dp[i][1] = dp[i - j * 3][1]; // 트리플은 싱글/불 개수 증가 없음
                    }
                }

                // 🔹 더블 (2배)
                if (i - j * 2 >= 0) {
                    if (dp[i][0] > dp[i - j * 2][0] + 1) {
                        dp[i][0] = dp[i - j * 2][0] + 1;
                        dp[i][1] = dp[i - j * 2][1];
                    }
                }

                // 🔹 싱글 (1배)
                if (i - j >= 0) {
                    if (dp[i][0] > dp[i - j][0] + 1) {
                        dp[i][0] = dp[i - j][0] + 1;
                        dp[i][1] = dp[i - j][1] + 1; // 싱글은 싱글/불 개수 증가
                    } else if (dp[i][0] == dp[i - j][0] + 1) {
                        dp[i][1] = Math.max(dp[i][1], dp[i - j][1] + 1);
                    }
                }
            }
        }
        return new int[]{dp[target][0], dp[target][1]};
    }
}

---

🧐 코드 분석

로직	설명
dp[i][0]	i 점수를 만들기 위한 최소한의 다트 횟수
dp[i][1]	i 점수를 최소 다트로 만들었을 때의 싱글/불 개수
점화식	dp[i] = min(dp[i - 가능한 점수] + 1)
싱글/불	dp[i][1] = max(dp[i][1], dp[i - 싱글 점수][1] + 1)

---

🚀 시간복잡도 분석

• target ≤ 100,000
• DP (O(target * 20) ≈ O(2,000,000)) → 충분히 최적화됨
• 완전 탐색 O(4^target) 대비 현저히 빠름! ⏩

---

🎯 결론

✅ 완전 탐색 (DFS, BFS)은 비효율적 → DP로 최적화
✅ 점화식 적용 (dp[i] 이용) → 이전 계산 결과를 재사용하여 시간 단축
✅ 최소 다트 횟수 & 싱글/불 최대 개수 반영
✅ Bottom-Up 방식 사용하여 최적화된 연산 진행 🚀

---

🔹 추가 최적화 가능성

1. 배열 크기 감소 (dp[100000][2] 대신 dp[2][100000] 형태로 변환 가능)
   • dp[i % 2]로 공간 최적화 가능 (이전 값만 유지하면 됨).
2. 트리플/더블 점수 미리 배열로 저장 → 반복문 최적화

   int[] triple = {3, 6, 9, ..., 60}; // 미리 저장  
   int[] double = {2, 4, 6, ..., 40}; // 미리 저장  

---

💡 최적화 결론

✔ 현재 코드 시간복잡도 O(target * 20)로 충분히 최적화됨
✔ 추가 최적화 가능하지만, 현재 상태로도 문제 해결 충분
✔ 점화식을 빠르게 떠올리는 것이 DP 문제 해결의 핵심! 🚀

---