[프로그래머스 Lv.3] 카운트 다운

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

프로그래머스

 

문제를 풀다가

dp라는 건 파악했는데

dp를 어떻게 활용해야할지 몰라 힌트를 참고했습니다.

 

이 문제는 dp로 접근해야합니다.

처음에는 단순하게

"50을 넘어가면 무조건 불로 점수를 메긴다"

라고 생각을 했었습니다.

하지만 60처럼, 바로 다트하나로 점수를 얻을 수 있는 방법이 있어서

60의 결과값은 [1,0]이 되어야합니다.

 

dp를 쓴다는 건 알았지만

그 다음 구체적은 구현이 까다로웠습니다.

처음에는 50 이하의 케이스에 대해서

dp를 넣은 후에 하나씩 찾아가는 방식.

예를들어, dp[51]이라면

dp[51]=dp[51-50]+1

이런 식으로 구현.

그런데, 이 경우도 60같은 케이스를 반영하지 못해서

오류가 발생했습니다.

 

힌트를 참고하다가

bottom-down을 사용해야한다는 걸 깨달았습니다.

 

60과 61의 예시입니다.

 

60을 만드는 경우는

50+10 혹은 60 이렇게 두가지입니다.

이 중, 다트를 가장 적게 사용하는 건

한번에 60에 꼳는 경우

따라서 결과는 [1,0]

 

61을 만다는 경우는

60+1 혹은 50+11

둘 다 2개의 다트를 쓰지만

50+11이 불&싱글 2개를 사용하기 때문에

결과값은 [2,2]

 

이렇듯, 모든 케이스를 구한 후에 

최소 다트/최대 불&싱글 순으로 정렬을 해야합니다.

 

import sys

limit_number = 300000
sys.setrecursionlimit(limit_number)
seq = [1, 18, 4, 13, 6, 10, 15, 2, 17, 3, 19, 7, 16, 8, 11, 14, 9, 12, 5, 50, 20]
cache = {}


def solution(target):
    answer = []

    def dp(n):
        if n == 0:
            return [0, 0]

        if n in cache:
            return cache[n]

        arr = []

        for i in seq:
            # 불
            if i == 50:
                if n - 50 >= 0:
                    temp = dp(n - 50)
                    arr.append((temp[0] + 1, temp[1] + 1))

            # 이외의 경우들
            else:
                # 어떤 게 최선인지 모르므로, 싱글 더블 트리플 모든 경우를 다 구한다

                # 싱글
                if n - i >= 0:
                    temp = dp(n - i)
                    arr.append((temp[0] + 1, temp[1] + 1))
                # 더블
                if n - i * 2 >= 0:
                    temp = dp(n - i * 2)
                    arr.append((temp[0] + 1, temp[1]))
                # 트리플
                if n - i * 3 >= 0:
                    temp = dp(n - i * 3)
                    arr.append((temp[0] + 1, temp[1]))

        # 다트 수/싱글&불 수로 정렬
        arr.sort(key=lambda x: (x[0], -x[1]))
        cache[n] = arr[0]
        return arr[0]

    answer = dp(target)

    return answer

 

dp문제 중 전형적이지만 까다로운 유형이므로

한번쯤 정리해보면 좋을 문제입니다.