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

🥚문제

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = [int(input().strip()) for _ in range(n)]

dp = [1] + [0]*k  # dp[0] = 1

for coin in coins:
    for i in range(1, k+1):
        if i - coin >= 0:
            dp[i] += dp[i-coin]
    """
    print(coin, "원짜리 동전까지를 사용했을 때")
    print(dp)
    print("-"*10)
    """

print(dp[k])

---

🧂아이디어

• k원이 되는 경우의 수 -> i원이 되는 경우의 수 (1 <= i <= k)로 나누어 접근

• i원이 되는 경우의 수를 구할 때, j번째 (1 <= j <= n)동전까지 사용했을 때 i원을 만들 수 있는 경우의 수로 또다시 나누어 접근

• 1차원 리스트 dp를 만들고, 동전 리스트 coins를 순회하며 업데이트 해준다.

• dp[i] = dp[i] + dp[ i - coins[j] ] (i - coin[j] >= 0일 때)

• RHS의 dp[i] + dp[ i-coins[j] ]에 대해서 설명하자면,

  • dp[i]: j-1번째 동전까지 사용해서 i원을 만드는 경우의 수 (업데이트 전)
  • dp[ i-coins[j] ]: j-1번째 동전까지 사용했을 때, (i - coin[j])원을 만드는 경우의 수.
    이것을 더하는 이유는, 각 경우에 현재 동전인 coins[j]만 추가하면 우리가 만들고 싶은 i원이 되기 때문.
    (새로운 경우를 만드는 것이 아니라 원래 경우에 coins[j]만 추가되는 형태이므로 dp[ i-coins[j] ]의 값 그대로 갖다 쓸 수 있음)

• 이때, dp[0] = 1로 초기화해줘야 함에 유의
  -> 동전이 하나만 쓰일 경우에 이용하는 값

🔽코드의 주석 부분에서 출력되는 값🔽

참고❤: https://mong9data.tistory.com/68