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

카운트 다운

링크

코딩테스트 연습 - 카운트 다운

[ 문제에 대한 이해 ]

• 다트 과녁에는 1부터 20까지의 수가 있고, 각 수마다 싱글, 더블, 트리플 칸이 있다.
• 최소한의 횟수로 점수를 0점으로 만드는 것이 1순위이다.
• 만약 최소한의 횟수로 만드는 방법이 여러가지가 있다면, 싱글 또는 불을 최대한 많이 던지는 방법을 사용해야 한다.

접근 방법

제한 사항을 확인한다.

• target은 1부터 10만의 범위를 가지기 때문에, 최대한 적은 시도 횟수로 탐색을 시도해야 한다.

탐색 횟수가 적은 방법으로 접근할 수 있는 방법은 그리디와 다이나믹 프로그래밍이 있다.

동전 문제를 생각해보자.

• 8이라는 금액을 1, 4, 5라는 동전으로 거슬러줄 수 있다고 생각하자. 5원을 내면 3원을 내기 위해 총 4개의 동전이 필요하지만, 4원을 낸다면 두 개의 동전만으로 8원을 만들 수 있다.

이 문제 또한 어떤 점수를 만들기 위해 필요한 다트 점수가 매우 다양하므로, 그리디로는 접근이 불가능하다.

또한 동전 문제와 동일하게 어떤 금액 i를 만들기 위해 4원의 동전을 내야 한다고 가정한다면, 3원을 만들기 위한 동전의 개수 + 1을 더한 값과 기존의 값 중 최솟값을 비교하여 반영하면 되고, 주어진 조건이 변하지 않으면 해당 금액에 대해서 늘 동일한 결과를 갖기 때문에 해당 값을 최종 해를 구하는 데 재사용할 수 있다.
따라서 다이나믹 프로그래밍으로 해결이 가능하다.

• 동전을 점수로 치환하면 동일한 원리로 해결이 가능함을 확인할 수 있다.

다만 이 경우는 한 뎁스 더 생각해야 할 필요가 있다.

최소의 다트 횟수로 점수를 완성하되, 같은 횟수라면 불 또는 싱글 횟수가 최대인 경우를 생각해줘야 한다.

따라서 싱글과 불로 만들수 있는 점수와, 싱글과 불로 만들 수 없는 점수를 나눈 테이블을 만들어 주었다.

# arr[0]은 싱글, 불로 만들 수 있는 점수
# arr[1]은 싱글, 불로 만들 수 없는 점수
def create_table():
    arr = []
    arr.append([i for i in range(1, 21)])
    arr[0].append(50)
    nxt = []
    for i in range(1, 21):
        for j in range(2, 4):
            ret = i * j
            if ret > 20:
                nxt.append(ret)
    arr.append(list(set(nxt)))
    return arr

시도 횟수와 최대 싱글 + 불 횟수 합을 저장해야 하므로, 2차원 배열로 dp배열을 선언한다.

모든 점수를 순회하면서 개수를 세되, 현재 최솟값과 동일한 시도 횟수라면, 최대 싱글 + 불 횟수를 저장할 수 있도록 한다.

정답 코드

INF = 987654321

def create_table():
    arr = []
    arr.append([i for i in range(1, 21)])
    arr[0].append(50)
    nxt = []
    for i in range(1, 21):
        for j in range(2, 4):
            ret = i * j
            
            if ret > 20:
                nxt.append(ret)
                
    arr.append(list(set(nxt)))
    
    return arr

def solution(target):
    table = create_table()

    dp = [[INF, 0] for _ in range(target + 1)]
    dp[0][0] = 0

    for i in range(1, target + 1):
        for j in range(2):
            for k in range(len(table[j])):
                prev = i - table[j][k]

                if prev < 0:
                    continue

                total, valid = dp[prev][0] + 1, dp[prev][1] + 1 - j

                if total < dp[i][0]:
                    dp[i] = [total, valid]
                    
                elif total == dp[i][0]:
                    dp[i] = [total, max(dp[i][1], valid)]

    return dp[target]