백준 2293 동전 1 파이썬 풀이

난이도 : 골드5

풀이일 : 2404033

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

2293번: 동전 1

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이코드

import sys

n, k = map(int, sys.stdin.readline().split())
coins = []  # 동전 종류

for _ in range(n):
    coin = int(sys.stdin.readline())
    coins.append(coin)

dp = [0] * (k + 1)  # 경우의 수
dp[0] = 1

for coin in coins:
    # 해당 동전으로 만들 수 있는 경우의 수 추가
    for i in range(coin, k + 1):
        dp[i] += dp[i - coin]

# k 값이 되는 경우의 수
print(dp[k])

• coins : 주어진 동전의 종류를 저장한다.
• dp : 각 인덱스 값을 만들 수 있는 경우의 수를 저장한다.
  • 동전들로 0을 만들 수 있는 경우의 수는 1 저장
  • 각 동전마다 동전 값부터 k값까지의 인덱스를 순회하며, 해당 동전을 추가해서 인덱스 값을 만들 수 있는 경우의 수를 합산해준다.
  • 모든 동전으로 반복문이 끝나면, 각 값에는 가지고 있는 동전들을 사용해 그 값을 만들 수 있는 경우의 수가 저장된다.

---

느낀점

• 아직 dp가 별로 익숙하게 느껴지지 않는다. solved.ac 보면서 내가 안 푼 유형의 문제들을 좀 골라두고 일주일에 몇 문제는 꼭 풀도록 강제해두던지 해야지.