백준 9084 동전

동전(백준 9084)

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

예상한 방식이 제대로 작동되지 않아
뭐가 잘못되었나 싶었었는데…
배열 0번째 값에 1을 넣어주는 것이 맞다는 것과,
(0원은 어떠한 동전이라도 ‘0’개를 더해주는 것으로 만들수 있으므로)
2중 반복문을 ‘동전’을 상위 반복문에 두는 것이 맞다는 점
(하나의 ‘동전’에 입장에서 해당 값을 표현하는 것이므로)

위 2 내용을 인식 후, 코드를 수정하여 통과하였다

Code

import sys

inp = sys.stdin.readline

testN = int(inp().strip())

for i in range(testN):
    cNum = int(inp().strip())           # 동전의 가지수는 1~20
    coins = list(map(int,inp().split())) # 동전은 중복되지 않는다
    mv = int(inp().strip())             # 목표 금액은 1~10000
    dp = [1] + [0] * mv                 # 경우의 수 dp 테이블 (0원은 어떤 동전값이라도 만들 수 있음)


    for j in range(cNum): # 코인 반복문 돌면서 체크하기
        for i in range(1,mv + 1):
            if coins[j] <= i:
                dp[i] += dp[i - coins[j]]

    print(dp[mv])

해결 아이디어

1. 동전의 경우의 수를 저장할 dp를 초기화
   (0에만 1을 넣어준뒤, 나머지는 0으로 초기화)
2. 하나의 동전씩 반복문을 돌며,
   해당 값(j)를 표현할 수 있다면, 이전의 dp 배열에서,
   자신을 더하기 전에 표현할 수 있는지를 확인 후 더해준다
   
3. 다른 동전들의 경우, 동전을 ‘더해서’ 표현하는 경우,
   기존의 동전에 있는 해당 위치의 dp배열에서 값을 가져와 더해준다