[프로그래머스] 카운트 다운 - Java

문제 링크

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

문제

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

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

다트 과녁에는 1 부터 20 까지의 수가 하나씩 있고 각 수마다 "싱글", "더블", "트리플" 칸이 있습니다. "싱글"을 맞히면 해당 수만큼 점수를 얻고 "더블"을 맞히면 해당 수의 두 배만큼 점수를 얻고 "트리플"을 맞히면 해당 수의 세 배만큼 점수를 얻습니다. 가운데에는 "불"과 "아우터 불"이 있는데 "카운트 다운" 게임에서는 구분 없이 50점을 얻습니다.

대회는 토너먼트로 진행되며 한 게임에는 두 선수가 참가하게 됩니다. 게임은 두 선수가 교대로 한 번씩 던지는 라운드 방식으로 진행됩니다. 가장 먼저 0점을 만든 선수가 승리하는데 만약 두 선수가 같은 라운드에 0점을 만들면 두 선수 중 "싱글" 또는 "불"을 더 많이 던진 선수가 승리하며 그마저도 같다면 선공인 선수가 승리합니다.

다트 실력에 자신 있던 종호는 이 대회에 출전하기로 하였습니다. 최소한의 다트로 0점을 만드는 게 가장 중요하고, 그러한 방법이 여러가지가 있다면 "싱글" 또는 "불"을 최대한 많이 던지는 방법을 선택해야 합니다.

목표 점수 target이 매개변수로 주어졌을 때 최선의 경우 던질 다트 수와 그 때의 "싱글" 또는 "불"을 맞춘 횟수(합)를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 <= target <= 100,000

알고리즘: DP

풀이

DP의 사용 조건은 동일한 작은 문제들이 반복하여 나타나는 경우 사용할 수 있다.
->(하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용)
DP를 사용하면 시간복잡도를 효율적으로 개선할 수 있기 때문에 사용할 수 있는 문제라면 적극적으로 활용하는 게 좋다.

위 개념을 인지하고 문제를 풀어보자, 우리의 목표는 점수가 target일 때 다트는 최대한 적게, "싱글"과 "불"은 최대한 많이 맞추는 것이 목표다.
목표를 달성하기 위해서 이런 아이디어가 생각나야 한다.
(해당 점수일 때 최선의 값) + 다트의 점수 ex) (dp[30] + 다트의 점수) -> 이 경우를 전부 따져서 (점수 + 다트 점수)를 최선의 값으로 만들어 주면 된다. 즉, 작은 문제로 큰 문제를 해결할 수 있기 때문에 DP를 사용한다.
경우의 수도 60 * 100,000이기 때문에 충분히 풀이가 가능하다.

소스 코드

import java.util.*;
class Score {
    int score;
    boolean sb;
    Score(int score, boolean sb) {
        this.score = score;
        this.sb = sb;
    }
}
class Node {
    int cnt, sb_cnt;
    Node(int cnt, int sb_cnt) {
        this.cnt = cnt;
        this.sb_cnt = sb_cnt;
    }
}
class Solution {
    static ArrayList<Score> score_list = new ArrayList<>();
    static Node[] dp;
    public int[] solution(int target) {
        int[] answer = new int[2];
        //다트판 모든 점수 넣기
        score_list.add(new Score(50, true));
        for(int i=1; i<=20; i++) {
            score_list.add(new Score(i, true));
            score_list.add(new Score(i*2, false));
            score_list.add(new Score(i*3, false));
        }
        dp = new Node[target + 61];
        dp[0] = new Node(0, 0);
        for(int i=0; i<=target; i++) {
            for(int j=0; j<score_list.size(); j++) {
                int next_score = i + score_list.get(j).score;
                int next_sb_cnt = score_list.get(j).sb ? dp[i].sb_cnt + 1 : dp[i].sb_cnt;
                if(dp[next_score] == null) dp[next_score] = new Node(dp[i].cnt + 1, next_sb_cnt);
                else {
                    if((dp[i].cnt + 1) < dp[next_score].cnt) dp[next_score] = new Node(dp[i].cnt + 1, next_sb_cnt);
                    else if((dp[i].cnt + 1) == dp[next_score].cnt) {
                        if(next_sb_cnt > dp[next_score].sb_cnt) dp[next_score].sb_cnt = next_sb_cnt;
                    }
                }
            }
        }
        answer[0] = dp[target].cnt;
        answer[1] = dp[target].sb_cnt;
        return answer;
    }
}