<Lv.3> 카운트다운 (프로그래머스 : C#)

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

📕 문제 설명

다트판은 1~20까지 수가 하나씩 있고 각 수마다 "싱글", "더블", "트리플" 칸이 존재한다. 각 칸 별로 다음의 점수를 획득한다.
싱글 : 해당 수
더블 : 해당 수 x 2
트리플 : 해당 수 x 3

가운데에는 "불"과 "아우터 불"이 있는데 구분 없이 50점을 얻는다.

대회는 토너먼트 형식으로 두 선수가 한 게임에 참여하며 교대로 한 번씩 던지는 라운드 방식으로 진행된다. 가장 먼저 0점을 만든 선수가 승리하는데 두 선수가 같은 라운드에 0점 만드는 경우에는 싱글 또는 불을 더 많이 던진 선수가 승리하며, 이것도 같으면 선공인 선수가 승리한다.

목표 점수가 주어질 때 최선의 경우 던질 다트 수와 그 때의 싱글 또는 불을 맞춘 횟수 합을 순서대로 배열에 담아 반환하기

(최선으로 던지기 위해서는 1) 최소한의 다트로 0점을 만드는 것 2) 싱글 또는 불을 최대한 많이 던지는 것 순서로 고려 필요)

• Input
  목표 점수
• Output
  최선의 경우 던질 다트 수, 그 떄의 "싱글" 또는 "불"을 맞춘 횟수 (합)

예제

풀이

다트 수와 싱글 불 횟수를 dp에 저장하여 가장 최적의 상황으로 갱신한다.

• dp[i,0] = i점을 만드는 최선의 다트 수, dp[i,1] = i점을 만드는 최선의 싱글, 불 횟수

불과 싱글, 더블, 트리플 모든 케이스에 대해 재귀로 다트 수와 싱글, 불 횟수를 확인하여 dp를 갱신해준 후 최종적으로 dp[target, 0]과 dp[target, 1]을 반환해준다.

using System;

public class Solution {
    const int MaxNum = 100000;
    int[,] dp; 
    public int[] solution(int target) {
        dp = new int[target + 1, 2]; // 0: 다트 수, 1: 싱글,불
        
        for (int i = 1; i <= target; i++)
        {
            dp[i, 0] = MaxNum;
        }
    
        return GetResult(target);
    }
    
    public int[] GetResult(int target)
    {
        if (dp[target, 0] != MaxNum) return new int[2] {dp[target, 0], dp[target, 1]};

        if (target >= 50) 
        {
            int[] temp = GetResult(target - 50); // 불 맞춘 후 결과 (횟수, 싱글/불)
            
            if (IsBetterCase(temp, target))
            {
                dp[target, 0] = 1 + temp[0];
                dp[target, 1] = 1 + temp[1];
            }
        }
        
        int start = target >= 20 ? 20 : target;
        // 모든 케이스 고려 
        for (int i = start; i >= 1; i--) // 1 ~ 20까지 
        {
            for (int j = 1; j <= 3; j++) // 싱글, 더블, 트리플
            {
                if (target < i * j) break;
                
                int[] temp = GetResult(target - i * j);
                int cnt = j == 1 ? 1 : 0; // 싱글일 경우 + 1
                if (IsBetterCase(temp, target))
                {
                    dp[target, 0] = 1 + temp[0];
                    dp[target, 1] = cnt + temp[1]; 
                }
            }
        }
        
        return new int[2] {dp[target, 0], dp[target, 1]};
        
    }
    
    public bool IsBetterCase(int[] temp, int target)
    {
        // 1. 다트 횟수 더 작거나 2. 다트 횟수 같고 싱글/불 횟수 더 많으면 갱신
        return temp[0] + 1 < dp[target, 0] || (temp[0] + 1 == dp[target, 0] && temp[1] + 1 > dp[target, 1]);
    }
}

결과