카운트 다운 (131129번) - 프로그래머스 (Programmers)

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

프로그래머스

 

프로그래머스 - 카운트 다운 (131129번)

 

난이도 : Lv 3

알고리즘 : Dynamic Programming

Time Complexity : O( N )

 

def solution(target):
    memo = [[0, 0] for _ in range(max(70, target)+1)]
    for i in range(1, 21):
        memo[i] = [1, 1]
    for i in range(21, 41):
        memo[i] = [1, 0]
    for i in (23, 25, 29, 31, 35, 37):
        memo[i] = [2, 2]
    for i in range(41, 50):
        memo[i] = [2, 1]
    memo[50] = [1, 1]
    for i in range(52, 71):
        memo[i] = [2, 2]
    for i in range(42, 61, 3):
        memo[i] = [1, 0]
    
    for i in range(71, target+1):
        sty = i-60
        fty = i-50
        tf = False
        if memo[sty][0] < memo[fty][0]:
            tf = True
        elif memo[sty][0] == memo[fty][0]:
            if memo[fty][1] < memo[sty][1]:
                tf = True
        if tf:
            memo[i] = [memo[sty][0]+1, memo[sty][1]]
        else:
            memo[i] = [memo[fty][0]+1, memo[fty][1]+1]
    
    return memo[target]

 

1~70까지 경우의 수

 

1~70까지 각자의 경우를 직접 구해보면 위와 같다.

 

그리고 앞에서 70까지는 구했으니,

만약 target이 70보다 크다면

71부터 구하기 시작하면 된다.

 

(x-50)과 (x-60) 비교

 

71을 예로 들면, 21(=71-50)과 11(71-60)을 비교해본다.

 

둘 중 다트 수가 적은걸 우선적으로 선택하고

만약 다트 수가 같다면, 싱글과 볼이 많은 경우를 선택한다.

 

이렇게 71부터 target까지 쭉 업데이트하면 된다.