[백준] 3067번 Coins

💡문제접근

• 대표적인 동적 프로그래밍 문제
• 손코딩하며 예제를 파악한 다음 코드로 옮겼다.

💡예제설명

1원, 2원, 3원으로 6원을 만드는 예제를 dp 테이블을 이용해서 설명

• dp테이블은 무엇을 의미하는가? → dp[i] : i원을 만드는데 나올 수 있는 모든 경우의 수

	0	1	2	3	4	5	6
0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1
2	1	1	2	2	3	3	4
3	1	1	2	3	4	5	7

최종적으로 dp 테이블을 1차원 배열로 바꿔 생각해보면 아래와 같다.

0	1	2	3	4	5	6
1	1	2	3	4	5	7

💡코드(메모리 : 31256KB, 시간 : 88ms)

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    coins = list(map(int, input().strip().split()))
    cost = int(input())

    dp = [0] * (cost + 1)
    dp[0] = 1   # 0원을 만들 수 있는 방법은 1가지

    # dp 테이블의 정의
    # dp[i] = i원을 만드는데 드는 경우의 수

    # 1원과 2원만 존재
    for i in range(N):
        # 1원만 사용할 경우
        # ex. 1원 만드는데 드는 경우의 수 : 1가지
        # ex. 2원 만드는데 드는 경우의 수 : 1가지
        # ex. 3원 만드는데 드는 경우의 수 : 1가지

        # dp 테이블 상태 : [1, 1, 1, 1]

        # 2원도 사용한다면?
        # ex. 1원 만드는데 드는 경우의 수 : 1가지
        # ex. 2원 만드는데 드는 경우의 수 : 2가지
        # ex. 3원 만드는데 드는 경우의 수 : 2가지

        # dp 테이블 상태 : [1, 1, 2, 2]
        for j in range(coins[i], cost+1):
            dp[j] = dp[j] + dp[j - coins[i]]
    print(dp[cost])

💡소요시간 : 37m