[BOJ] 백준 2293번 - 동전 1 (Python)

문제

문제 바로가기

해결

다이나믹 프로그래밍은 최적화 문제를 해결하는 알고리즘으로 늘 다음의 형태를 띄는지 확인해야한다.

• 전체 문제가 작은 부분 문제들로 나뉘어지는가? 즉 전체 문제를 풀기 위해 작은 부분 문제들의 조합인 점화식으로 작성될 수 있는가?

• 부분 문제들을 해결하며 얻는 결과값을 DP테이블에 기록(메모이제이션)하는 가?

• 점화식이 문제의 제약 및 관계를 모두 충족시키며 나아갈 수 있는가?

우선 위 문제를 다이나믹 프로그래밍을 활용하여 풀기 위해 우선적으로 큰 문제인 ‘가치의 합이 k원이 되는 동전 조합의 경우의 수’를 ‘1 <= i <= k‘원이 되는 동전 조합의 경우의 수를 구하는 부분 문제로 나누어 보았다.

우선 전체적인 문제의 접근방식은 다음과 같다.

coins에 존재하는 화폐 c마다 반복문을 돌리고, 각 반복문마다 c ~ k만큼의 i원을 만드는 경우의 수를 리스트에 더해준다.

예를 들어 설명하자면 화폐 c가 2이고, 2~k까지를 반복하는 i가 5라고 한다면 5-2가 양수이므로 d[5] = d[5] + d[3]인 것이다. 그리고 d[3]은 d[3] = d[3] + d[1]로 이루어져 있다. d[1], d[3], d[5]는 c가 1이었을 상황에 기록된 원소인 1, 1, 1이 저장되어 있으므로, c가 2일 경우 d[1], d[3], d[5]는 각각 1, 2, 3가 될 것이다. 그리고 이는 1과 2를 사용하여 1과 3과 5를 만드는 경우의 수를 나타낸다.

n, k = map(int, input().split())
coins = []
d = [0] * (k + 1)
d[0] = 1

for _ in range(n):
  coins.append(int(input()))

for c in coins:
  for i in range(c, k + 1):
    if i - c >= 0:
      d[i] += d[i - c]

print(d[k])