[백준][DP] 2293. 동전 1

2293. 동전1 

 

• DP라는 것
  • 작은 문제로 쌓아나가서 큰 문제를 해결할 수 있는 문제
  • 작은 문제에 하나하나씩 추가되어 나갈때의 변화를 보는 것

 

• 이 문제는 동전이 배수가 아니니까 상위동전이 무조건 좋은게 아닐 수 있다
  • →  그리디하게 못푸니까 dp 로 넘어감
  • 욕심을 부린다고 되는문제인가?
    • → 이런 경우는 동전이 배수일 경우
  • 그리디↔ DP 반대개념

ex)  12원을 만들려는데 10,6,1이 있어
욕심쟁이는 10원짜리 선택 → 1원 2개필요하니까 ⇒ 3
다이나믹하게 생각하면 10원짜리가 있지만, 최선이 아닐 수 잇다 ⇒  6원짜리가 있으니 6원 2개로 되겠다

• dp라는 것은 하나씩 추가되었을 때 변화되는 세계를 보는 것임

외국인에게 우리나라 화폐를 알려주는데 전부 한번에 알려주면 어렵겠지?

하나씩 생각하게 만들자

- 10원만 있다고 알려줬을 때 →  10,20,30,...을 만들수 있는 경우의 수를 생각함
- 10,50원만 있을 때 (50원이 추가되었을 때)
→   50, 100을 새로운 방법으로 낼 수 있는 방법이 플러스됨
- 10,50,100원만 있을 때 (100원이가 추가되었을 때)
→  100원을 낼수있는 새로운 방법도 업데이트

 

• 풀이
  • 그렇기때문에 동전부터 하나씩 확인하면서
  • 만들 수 있는 값의 방법을 점점 업데이트 해나가는 것

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

coins = []
for i in range(n):
    coins.append(int(input()))
coins.sort()

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