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

---

1. 코드

from collections import defaultdict

"""
target = 1~60 -> dp 초기값 hard coding
target = 61~  -> best(불(50)을 맞춘 경우, 불이 아닌 60점을 맞춘 경우)

60점을 맞춘 이유 -> 60점을 맞춘 화살은 [1, 0]의 best 효율을 가진다. 
"""
def solution(target):
    d = defaultdict(int)

    # (1~60)
    # init value set
    d[50] = [1, 1]
    for n in range(1, 21):
        d[n] = [1, 1]
    for n in [21, 22, 24, 26, 27, 28, 30, 32, 33, 34, 36, 38, 39, 40, 42, 45, 48, 51, 54, 57, 60]:
        d[n] = [1, 0]
    for n in [23, 25, 29, 31, 35, 37]:
        d[n] = [2, 2]
    for i in range(1, 61):
        if i not in d:
            if i >= 50:
                a, b = d[i - 50]
                d[i] = [1 + a, 1 + b]
            else:
                a, b = d[i - 20]
                d[i] = [1 + a, 1 + b]

    # (61~target)
    # ex) d[106] = d[50] + d[106-50] => 불값을 맞춘 경우
    #            = d[60] + d[106-60] => 불값을 맞추지 않았을 때의 최선인 60점을 맞춘 경우
    for num in range(61, target+1):
        a = [d[num - 50][0] + d[50][0], d[num - 50][1] + d[50][1]]  # 불(50점)
        b = [d[num - 60][0] + d[60][0], d[num - 60][1] + d[60][1]]  # 60점
        t = [a, b]
        d[num] = sorted(t, key=lambda x: (x[0], -x[1]))[0]  # a,b 중 최선의 값 선택

    return d[target]

---

2. 후기

초기값을 설정하는 것은 노가다로 금방 구할 수 있을 것 같아서 60까지 직접 입력했다. 61부터의 DP 로직은 단순하다. 불값을 맞춘 경우 와 60점을 맞춘 경우 중 최선의 값을 선택하면 된다.