[programmers/py] 카운트 다운

카운트 다운

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

문제 설명

• 싱글, 더블, 트리플, 불을 사용해서 결과를 계산
• 목표 점수 target이 매개변수로 주어졌을 때 최선의 경우 던질 다트 수와 그 때의 "싱글" 또는 "불"을 맞춘 횟수(합)를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

문제 풀이

• dp문제
• 1~70점까지는 싱글, 더블, 트리플, 불을 사용해서 결과를 계산
• 그 이상은 -50과 -60(트리플) 중 작은 값을 선택
• 참고 https://school.programmers.co.kr/questions/49069

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]