[Baekjoon 9084 / python / 골드5] 동전

import sys

input = sys.stdin.readline

T = int(input())  # 테스트 케이스 개수

for _ in range(T):  # 테스트 케이스 개수만큼 진행한다

    N = int(input())  # 동전 종류 개수

    coinBox = list(map(int, input().split()))  # 동전 입력받기

    coinBox.insert(0, 0)  # 0번 인덱스에 0넣기. 첫번째 동전부터 점화식을 적용하기 위함.

    money = int(input())

    dp = [[0] * (money + 1) for i in range(N + 1)]  # 목표금액만큼 한 행을 길게, 동전갯수만큼 한 열을 길게

    for i in range(N + 1):

        dp[i][0] = 1  # 동전이 뭐든 간에 0을 만드는 경우의 수는 항상 1

    for x in range(1, N + 1):  # 동전 종류만큼 반복

        for y in range(1, money + 1):  # 각 동전 당 목표금액까지 반복한다

            dp[x][y] = dp[x-1][y]

            if y-coinBox[x] >= 0:  # 목표금액 - 현재동전가치가 0 이상이면

                dp[x][y] += dp[x][y-coinBox[x]]  # DP테이블 내에 값이 있는 것이므로 그 값을 더해주기(이전 동전 경우의수를 더해주는 것)

    print(dp[N][money])

 

다이나믹 프로그래밍 문제이다. 점화식을 알면 비교적 간단하게 풀 수 있는데, 그 점화식을 찾는게 굉장히 문제다.

 

dp : dp 테이블, x는 행 y는 열

money : 목표 금액

coinBox : 동전이 담긴 리스트

 

아래는 점화식이다.

dp[x][y] = dp[x-1][y]    ->  dp테이블에서 바로 위 값을 받아온다.

if y-coinBox[x] >= 0:    -> (현재 목표 돈 - 현재 동전 가치) 결과가 0 이상이라면 ( 좌표를 찾는 것이다. 즉, dp테이블에 존재하면 )

dp[x][y] += dp[x][y-coinBox[x]]    -> 기존 값에 해당 값을 더한다.

 

이게 끝이다. 솔직히 왜 이렇게 되는 건진 정확히 모르겠다. 도저히 답이 안 보여서 다른 분의 글을 참고해서 풀었다.

DP가 어렵다 어렵다 하는 말은 많이 들었는데 그게 이런 뜻일 줄이야...