[BOJ] 2293 - 동전 1 (🥈 실버 1티어, 냅색 알고리즘)

사용 언어: Python3

문제

동전 1

풀이

참고

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

# dp: 동전의 가치의 합이 index 라고 할 때, 그 경우의 수
dp = [1] + [0] * k # 0원은 아무 코인도 안 쓰면 되니 경우의 수가 하나다!

for val in coin:
    for j in range(val, k+1):
        dp[j] += dp[j-val]

print(dp[k])

• 테스트 케이스: 통과
• 제출 결과: 통과
  

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기