프로그래머스 lv3 카운트다운

1. 개요

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

2. 풀이

def solution(target):
    NMAX, DARTMAX = target+1, 21
    DARTS, SINGLEBOOL = [NMAX]*NMAX, [NMAX]*NMAX
    DARTS[0] = SINGLEBOOL[0] = 0

    # single과 bool을 모두 일단 던져본다.
    # 최적의 총 다트수와 싱글과 불의 다트수를 구할수 있다.
    
    # single
    for dart in range(1, DARTMAX):
        for i in range(dart, NMAX):
            SINGLEBOOL[i] = DARTS[i] = min(DARTS[i], DARTS[i-dart]+1)
    
    # bool
    for i in range(50, NMAX):
        SINGLEBOOL[i] = DARTS[i] = min(DARTS[i], DARTS[i-50]+1)
    
    # 이제 더블과 트리플을 던져본다.
    # 만약 더 최적이라면 총다트수와 싱글과 불의 다트수를 갱신해준다.
    # 총다트수가 같아도 싱글과 불의 다트수를 다를수 있기때문에 갱신이 필요하다!
    # 이때 갱신되는 싱글과 불의 다트수는 현재 점수에서 던진 다트를 빼었을때 싱글과 불의 다트수이다.
    for dart in range(1, DARTMAX):
        dart *= 2
        for i in range(dart, NMAX):
            if DARTS[i-dart]+1 < DARTS[i]:
                DARTS[i], SINGLEBOOL[i] = DARTS[i-dart]+1, SINGLEBOOL[i-dart]
            elif DARTS[i-dart]+1 == DARTS[i]:
                SINGLEBOOL[i] = max(SINGLEBOOL[i], SINGLEBOOL[i-dart])
    # triple
    for dart in range(1, DARTMAX):
        dart *= 3
        for i in range(dart, NMAX):
            if DARTS[i-dart]+1 < DARTS[i]:
                DARTS[i], SINGLEBOOL[i] = DARTS[i-dart]+1, SINGLEBOOL[i-dart]
            elif DARTS[i-dart]+1 == DARTS[i]:
                SINGLEBOOL[i] = max(SINGLEBOOL[i], SINGLEBOOL[i-dart])

    return [DARTS[-1], SINGLEBOOL[-1]]