내일은 알고리즘

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

https://www.acmicpc.net/problem/9084

1. 이해 (5분) - 2분

01knapsack 유형의 문제입니다. 워낙 유명한 DP문제라 따로 설명은 하지 않겠습니다.

풀이방법은 간단합니다. 우선 어떤 동전의 값이 V이라고 하면 당연히 V금액을 만드는것이 가능합니다.

그리고 만약 M이라는 금액을 만드는 방법이 있다면 우리는 V짜리 동전 하나를 더해 간단히 M+V를 만들 수 있습니다.

2. 계획 (5분) - 2분

위에서 이해한 개념을 바탕으로 계획을 세워봅시다.

사용가능한 동전의 값들을 입력받고, 크기 M+1짜리 배열을 만듭니다.

우리는 이 배열에 0원부터 순차적으로 그 금액에 가능한 가짓수를 구하고 최종적으로 M원을 만들 수 있는 가짓수를 구할것입니다.

동전의 갯수 N만큼 반복해야하는 작업은 이렇습니다.

1. V짜리 동전을 가지고 금액 V를 만드는건 당연히 가능하다. (1가지 방법)

2. 만약 M이라는 금액을 만드는 방법이 X개 있다면, 그 X가지 방법에 V짜리 동전을 더해 M+V금액을 만들 수 있다. (X가지 방법) 

이 두가지 작업을 마치면 최종적으로 주어진 동전들로 M원을 만들 수 있는 방법의 수를 구할 수 있습니다.

3. 검증 (5분) - 1분

만약 중복조합같은 방식으로 문제를 풀려고 했다면 문제가 생겼겠지만, 구상한 방식에서 M짜리 배열의 크기는 1만에 불과하고 동전과 테스트케이스도 20,10개이므로 시간초과가 발생하지는 않을 것 같습니다.

4. 풀이 (30분) - 13분

파이썬을 사용했고 문제의 풀이방법만 알고 있다면 간단히 작성가능한 코드라 금방 끝났습니다.

5. 채점, 디버깅 (+5분)

첫 제출에서 런타임에러가 발생했습니다! 동전의 값어치와 금액 M 사이에 대소관계가 없어 발생한 Index에러였습니다.

(만약 만들 금액이 30원인데, 100원짜리, 500원짜리 동전을 사용하려고 하면..? DP배열의 index를 넘어간다!) 

동전의 값어치가 금액보다 클때 반복문을 통과하는 조건문을 만들어주어 통과했습니다.

import sys

T = int(sys.stdin.readline())
sb = ""

for t in range(T):
    N = int(sys.stdin.readline())
    coin = list(map(int, sys.stdin.readline().split(' ')))
    M = int(sys.stdin.readline())
    dp = [0] * (M + 1)

    for n in range(N):
        dis = coin[n]
        if(dis > M):
            continue
        dp[dis] += 1
        
        for i in range(dis+1, M+1):
            dp[i] += dp[i-dis]

    sb += str(dp[M]) + "\n"

print(sb)