BOJ 2293 동전 1

LONGNEW·2021년 3월 28일
0

BOJ

목록 보기
212/333

https://www.acmicpc.net/problem/2293
시간 0.5초, 메모리 4MB
input :

  • n k(1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)
  • n개의 줄에는 각각의 동전의 가치가 주어진다.(1 <= 동전 <= 100,000)

output :

  • 경우의 수를 출력.

조건 :

  • 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

참고

점화식을.... 생각하지 못해서 위의 분의 풀이를 보았다.
가지고 있는 동전의 가치들을 이용해서 idx - coin[i]에 해당 하는 dp의 값을 더해주는 방식을 이용해야 한다.

동전이 몇개나 들어올지 모르는 상태이기도 하고, 그래서 각 동전에 대한 점화식이 필요하다.

dp[i] += dp[i - item] 현재 돈 - 동전의 가치. 이를 통해서 몇가지 경우가 있는지를 알 수 있다.

인제 나도 박스로 해서 모든 경우를 그려보자...

import sys

n, k = map(int, sys.stdin.readline().split())
coin = []
for i in range(n):
    coin.append(int(sys.stdin.readline()))

dp = [0] * (k + 1)
dp[0] = 1

for item in coin:
    for i in range(1, k + 1):
        if i - item >= 0:
            dp[i] += dp[i - item]
print(dp[k])

0개의 댓글