문제

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

---

입력

목표 점수 target

---

출력

최선의 경우 던질 다트 수와 그 때의 "싱글" 또는 "불"을 맞춘 횟수(합)

---

풀이

제한조건

• 1 ≤ target ≤ 100,000

접근방법

한 번에 얻을 수 있는 점수의 최대점은 60점.
다트의 수를 최소한으로 던지면서, 싱글과 불의 수는 가장 많아야 하며, 전체 점수는 100,000점 까지 주어질 수 있다.

따라서 단순 탐색으로 할 경우, 시간초과가 발생할 것이라 판단했다.

그렇다면 DP를 이용해서 문제를 풀어야 할 것 같은데 어떤식으로 접근할 수 있을까.

배열을 2개 만들어 해결하자.
하나는 K점을 만들기 위해 던져야하는 최소 다트의 수를 담고,
나머지 하나는 K점을 만들기 위해 던진 싱글과 불의 수를 담는다.

간단하게 생각해보자.

목표 : 24점을 최소한의 다트를 던지고, 최대한의 싱글과 불 던지기.

1. 24점을 만들기 위해, 24-X점을 만들고 X점을 던진다.
	a. 24-X점을 만들기 위해 던진 다트의 수 + 1
    b. 만약 X점이 싱글 또는 불이라면,
    	24-X점을 만들기 위해 던진 싱글+불의 수 +1
2. 그럼 이제 24-X점을 만들기 위한 방법의 수를 찾아야한다.
	이는 1의 과정에서 점수만 변경되고 동일한 로직의 반복이다.

위의 과정을 수행할 것이다.
DP문제의 특성상 상향식, 하향식 어떤방식으로도 접근은 가능하나, 재귀의 호출과 같은 오버헤드로 인해 상향식으로 접근한다.

1. 1점을 만들기 위해 나오는 경우 탐색.
2. 1의 결과를 이용해 2점을 나오는 경우 탐색.
3. 2의 결과를 이용해 3점이 나오는 경우 탐색
4. N-1까지의 결과를 이용해 N점이 나오는 경우 탐색.

---

코드

class Solution {
    public int[] solution(int target) {
        int[] darts = new int[target + 1]; // K점을 만들기 위해 던진 다트의 수.
        int[] count = new int[target + 1]; // K점을 만들기 위해 던진 싱글 + 불의 수
        
        // k점을 만들기 위한 경우의 수 탐색
        for(int i = 1; i <= target; ++i){
            // 최소 갯수를 던져야 하므로, 최대값으로 초기화 한다.
            darts[i] = Integer.MAX_VALUE;
            
            // 각 다트는 1~20 사이의 수이다.
            // 싱글 또는 불을 최대한 많이 던질 수록 유리하므로, 더블 트리플을 먼저 계산한다.
            for(int j = 1; j <= 20; ++j){
                // Case : Double
                int doubleScore = i - (2 * j);
                // 만들고자 하는 점수는 0점 보다 커야한다.
                if(doubleScore >= 0){
                    // 던진 다트의 수가 적다면 적은쪽으로 기록한다.
                    if(darts[doubleScore] < darts[i]){
                        darts[i] = darts[doubleScore] + 1;
                        count[i] = count[doubleScore];
                    }
                }
                // Case : Triple
                int tripleScore = i - (3 * j);
                if(tripleScore >= 0){
                    if(darts[tripleScore] < darts[i]){
                        darts[i] = darts[tripleScore] + 1;
                        count[i] = count[tripleScore];
                    }
                }
                
                // Case : Single
                int singleScore = i - j ;
                if(singleScore >= 0){
                    if(darts[singleScore] < darts[i]){
                        darts[i] = darts[singleScore] + 1;
                        count[i] = count[singleScore] + 1;
                    }
                }
            }
            
            // Case : Bull
            int bullScore = i - 50;
            if(bullScore >= 0){
                if(darts[bullScore] < darts[i]){
                    darts[i] = darts[bullScore] + 1;
                    count[i] = count[bullScore] + 1;    
                }
            }
        }
        
        return new int[] {darts[target], count[target]};
    }
}