(C#) 카운트 다운

https://school.programmers.co.kr/learn/courses/30/lessons/131129?language=csharp

프로그래머스

 

동적 프로그래밍으로 풀었다.

 

i = 0부터 target 까지, dp[i]에 i점을 얻기 위한 최소 다트 횟수, 최대 싱글 또는 불 횟수를 기록한다.

i가 20 이하라면 싱글 한번으로 된다.

i가 40 이하이고 2의 배수라면 더블 한번으로 된다.

i가 60 이하이고 3의 배수라면 트리플 한번으로 된다.

i가 50이라면 불 한번으로 된다.

그 외의 경우에는, i에서 j*t값을 빼준 점수에 싱글, 더블, 트리플 중 하나를 더하면 된다.

혹은 i에서 50을 빼준 점수에서 불을 한번 더하면 된다.

 

코드

using System;

public class Solution {
    public int[] solution(int target)
    {
        int[] answer = new int[] { };
        tuple[] dp = new tuple[100001];

        for (var i = 0; i <= target; i++)
        {
            if (i <= 20)
            {
                dp[i] = new tuple(1, 1);
                continue;
            }
            if (i <= 40 && i % 2 == 0)
            {
                dp[i] = new tuple(1, 0);
                continue;
            }
            if (i <= 60 && i % 3 == 0)
            {
                dp[i] = new tuple(1, 0);
                continue;
            }
            if (i == 50)
            {
                dp[i] = new tuple(1, 1);
                continue;
            }
            tuple temp;
            dp[i] = new tuple(dp[i - 1].u + 1, dp[i - 1].v);
            for (var j = 1; j <= 20; j++)
            {
                for (var t = 1; t <= 3; t++)
                {
                    if (i - j * t < 0) break;
                    temp = dp[i - j * t];
                    if (t == 1)
                    {
                        // 싱글
                        temp = new tuple(temp.u + 1, temp.v + 1);
                    }
                    else
                    {
                        // 더블 or 트리플
                        temp = new tuple(temp.u + 1, temp.v);
                    }

                    if (temp.u < dp[i].u || (temp.u == dp[i].u && temp.v > dp[i].v))
                    {
                        dp[i] = temp;
                    }
                }
            }
            if (i - 50 < 0) continue;
            temp = dp[i - 50];
            temp = new tuple(temp.u + 1, temp.v + 1);
            if (temp.u < dp[i].u || (temp.u == dp[i].u && temp.v > dp[i].v))
            {
                dp[i] = temp;
            }
        }
        answer = new int[2] { dp[target].u, dp[target].v };
        return answer;
    }

    struct tuple
    {
        public int u;
        public int v;
        public tuple(int u, int v)
        {
            this.u = u;
            this.v = v;
        }
    }
}