백준 2293 : 동전 1 [파이썬]

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

2293번: 동전 1

 

1. 문제설명

동적 계획법(Dynamic Programming, DP)은 최적화 문제를 해결하는 알고리즘으로서, 아래의 내용을 항상 명심해야 한다.

• '전체의 문제'를 '부분 문제'로 잘 나누었는가? 그렇다면 전체 문제를 해결하기 위한 부분 문제의 점화식은 무엇인가?
• 부분 문제들을 해결하며 얻는 결과값을 메모이제이션하는가?
• 부분 문제의 점화식은 부분 문제들 사이의 '관계'를 빠짐없이 고려하는가?

2293번의 문제 핵심은 다음과 같다.

• '가치의 합이 k원이 되는 경우의 수'를 구하는 전체의 문제를, '가치의 합이 i (1 ≤ i ≤ k)원이 되는 경우의 수'를 구하는 부분 문제로 나눈다. 추가적으로 부분 문제를 더욱 세부적으로 나눌 것인데, '특정 동전을 썼을 때 가치의 합이 i원이 되는 경우의 수'를 구하는 부분 문제로 나눈다.
• 위에서 언급한 부분 문제들을 해결해나가며 메모이제이션을 할 것인데, 시간 제한이 0.5초이며 메모리 제한도 4MB밖에 되지 않기 때문에 하나의 리스트 안에서 덮어 씌우는 식으로 빠르게 해결해나가야 한다.

 

n, k = map(int, input().split())

coin = [int(input()) for _ in range(n)]
dp = [0]*(k+1)
dp[0] = 1

for i in coin:
    for j in range(i, k+1):
        dp[j] += dp[j-i]

print(dp[k])

합이 i원이 되는 경우의 수를 구하기 위해 리스트 dp에 0을 k+1개 초기화한다. dp[1]은 합이 1원이 되는 경우의 수, dp[2]는 합이 2원이 되는 경우의 수,... , dp[k]는 합이 k원이 되는 경우의 수이다.

첫 번째 for문에서는 각 코인의 종류를 전부 순회한다. 입출력 예시의 경우, 1원 - 2원 - 5원 순으로 순회한다.

dp를 순회하며 특정 가치를 가진 동전을 썼을 때 합이 j원이 되는 경우의 수가 있다면 리스트 dp에 기록하기 위한 for문이다. 만약 동전이 3원짜리라면 dp[1], dp[2]는 고려할 필요가 없으므로 dp[3]부터 순회한다.