백준 / 동전 1 / 2293번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 동전 1 / 2293번 (골드 4단계)

문제 사이트: https://www.acmicpc.net/problem/2293

 

문제 설명

---

나의 풀이

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

coins = [int(input()) * 1 for _ in range(n)]

coins.sort()

dp = [0] * (m + 1)
dp[0] = 1
for c in coins:
    for i in range(c, m + 1):
        dp[i] += dp[i - c]
print(dp[m])

코드는 간단하지만 DP를 이용하는 과정에서 점화식을 세우는 과정이 조금 어렵다.

예시 입력을 봤을 때

1-1-1-1-1-1-1-1-1-1 = 10(1번째)

1-1-1-1-1-1-1-1-2 = 10(2번째)

1-1-1-1-1-1-2-2 = 10(3번째)

...

이 과정을 점화식으로 표현한 것이다.

다른 예로

2 3

1

3

1-1-1 = 3(1번째)

dp[1] = 1, dp[2] = 1, dp[3] = 1이다.

그 다음 과정에서 c == 3일 경우 dp[3] = dp[3] + dp[0] = 2가 출력되게 된다.

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/175

[알고리즘] 동적계획법(Dynamic Programming)