[Programmers] 카운트 다운 (Java)

1.  문제 링크

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

2.  문제

프로그래머스 다트 협회에서는 매년마다 새로운 특수 룰으로 다트 대회를 개최합니다. 이번 대회의 룰은 "카운트 다운"으로 "제로원" 룰의 변형 룰입니다.
"카운트 다운"은 게임이 시작되면 무작위로 점수가 정해지고, 다트를 던지면서 점수를 깎아서 정확히 0점으로 만드는 게임입니다. 단, 남은 점수보다 큰 점수로 득점하면 버스트가 되며 실격 합니다.

다음 그림은 다트 과녁입니다.

다트 과녁에는 1 부터 20 까지의 수가 하나씩 있고 각 수마다 "싱글", "더블", "트리플" 칸이 있습니다. "싱글"을 맞히면 해당 수만큼 점수를 얻고 "더블"을 맞히면 해당 수의 두 배만큼 점수를 얻고 "트리플"을 맞히면 해당 수의 세 배만큼 점수를 얻습니다. 가운데에는 "불"과 "아우터 불"이 있는데 "카운트 다운" 게임에서는 구분 없이 50점을 얻습니다.
대회는 토너먼트로 진행되며 한 게임에는 두 선수가 참가하게 됩니다. 게임은 두 선수가 교대로 한 번씩 던지는 라운드 방식으로 진행됩니다. 가장 먼저 0점을 만든 선수가 승리하는데 만약 두 선수가 같은 라운드에 0점을 만들면 두 선수 중 "싱글" 또는 "불"을 더 많이 던진 선수가 승리하며 그마저도 같다면 선공인 선수가 승리합니다.
다트 실력에 자신 있던 종호는 이 대회에 출전하기로 하였습니다. 최소한의 다트로 0점을 만드는 게 가장 중요하고, 그러한 방법이 여러가지가 있다면 "싱글" 또는 "불"을 최대한 많이 던지는 방법을 선택해야 합니다.
목표 점수 target이 매개변수로 주어졌을 때 최선의 경우 던질 다트 수와 그 때의 "싱글" 또는 "불"을 맞춘 횟수(합)를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

3.  제한사항

• 1 ≤ target ≤ 100,000

입출력 예

4.  소스코드

import java.util.*;

class Solution {
    int[][] dp;
    HashSet<Integer> singleAndBull, doubleAndTriple;
    public int[] solution(int target) {
        init(target);
        return getMinDartNum(target);
    }

    public void init(int target) {
        dp = new int[target + 1][2];

        for(int score = 1; score <= target; score++)
            dp[score][0] = Integer.MAX_VALUE;

        singleAndBull = new HashSet<>(); doubleAndTriple = new HashSet<>();
        singleAndBull.add(50);
        for(int point = 1; point <= 20; point++)
            singleAndBull.add(point);

        for(int point = 1; point <= 20; point++) {
            for(int muiltiple = 2; muiltiple <= 3; muiltiple++) {
                if(point * muiltiple <= 20) continue;
                doubleAndTriple.add(point * muiltiple);
            }
        }
    }

    public int[] getMinDartNum(int point) {
        if(point == 0) return new int[] {0, 0};
        if(point < 0) return new int[] {Integer.MAX_VALUE, Integer.MAX_VALUE};
        if(dp[point][0] != Integer.MAX_VALUE) return dp[point];

        int[] result = new int[] {Integer.MAX_VALUE, 0};
        for(int sb : singleAndBull) {
            int[] midResult = getMinDartNum(point - sb);
            if(midResult[0] == Integer.MAX_VALUE) continue;
            findMin(result, new int[] {midResult[0] + 1, midResult[1] + 1});
        }
        for(int dt : doubleAndTriple) {
            int[] midResult = getMinDartNum(point - dt);
            if(midResult[0] == Integer.MAX_VALUE) continue;
            findMin(result, new int[] {midResult[0] + 1, midResult[1]});
        }

        return dp[point] = result.clone();
    }

    public void findMin(int[] result, int[] midResult) {
        if(result[0] > midResult[0])
            System.arraycopy(midResult, 0, result, 0, midResult.length);
        else if(result[0] == midResult[0])
            if(result[1] < midResult[1]) result[1] = midResult[1];
    }
}

5.  접근

• 2차원 dp 배열을 생성합니다. 이 배열은 각 점수에서 사용한 다트의 수와 싱글 또는 불을 맞춘 횟수를 나타냅니다.
  • dp[score][0] = score까지 진행했을 때 사용한 다트의 수
  • dp[score][1] = score까지 진행했을 때 맞춘 싱글 또는 불의 횟수
• 두 개의 HashSet singleAndBull, doubleAndTriple을 만드는데 singleAndBull에는 싱글 및 불에서 나올 수 있는 점수들을 담고, doubleAndTriple에는 더블 또는 트리플에서 나올 수 있는 점수들을 담습니다.
• 재귀를 통해 0점을 만드는 경우들에서 다트를 최소로 사용하고 싱굴 또는 불을 최대한 많이 던지는 경우를 찾습니다.
  • 만약 현재 point가 0이라면 목표에 도달했기 때문에 [0, 0]을 반환합니다.
  • 만약 point가 0보다 작다면 버스트가 되어 실격되기 때문에 [INF, INF]를 반환합니다.
  • 만약 현재 point에 이미 사용한 다트의 수가 저장되어있다면 이미 해당 point에 도달한 적이 있다는 뜻이므로 이를 그대로 이용하기 위해 dp[point]를 반환합니다.
  • 위 경우 모두에 해당되지 않는다면 싱글 또는 불을 최대한 많이 맞춰야 하기 때문에 싱글 또는 불로 맞추는 경우들부터 확인하고 이후에 더블 또는 트리플을 맞추는 경우들을 재귀를 통해 확인합니다.
  • 재귀를 통해 값이 반환될텐데, 이를 이용하여 dp의 값을 갱신합니다.
    • 만약 현재 dp 값보다 반환된 값이 더 적은 다트를 사용했거나 같은 다트 수를 사용했는데 싱글 또는 불을 더 많이 맞췄다면 해당 값으로 dp를 갱신합니다.