백준 :: 동전1 <2293번>

> 문제 <

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

> 해결 아이디어 <

n = 동전의 개수, k = 목표 동전 가치 합 (단위: 원)
각 동전 가치의 경우 하나씩 돌려가면서 최종 합 k를 충족하는 경우의 수 갱신하기
dp = [ index = 합, value = 주어진 동전들로 합을 만들 수 있는 경우의 수 ]
ex. dp[4] : 합이 4가 되는 경우의 수

코드 中 예시)
i == 5 & j == 6 인 경우,
j-i (1) >= 0 조건을 통과하므로 dp[6] += dp[1] 수행
-> 합 6에서 현재 동전가치(5)을 빼도 양수 (5+1=6)
그럼 dp[6](합 6이 되는 경우의 수)에 dp[1](합 1이 되는 경우의 수)를 더해주면, 합 6으로 만들 수 있는 경우의 수가 갱신되는 것이다. (현재 동전 5원일 경우에)

dp[6]+=dp[1] : 5원을 제외한 동전들로 합 1이 되는 경우 + 5원 (5원+1원) 갱신!
dp[8]+=dp[3] : 5원을 제외한 동전들로 합 3이 되는 경우 + 5원 (5원 + 1원+1원+1원, 5원+ 1원+2원) 갱신!


출처: https://mong9data.tistory.com/68

> 코드 <

n,k = map(int, input().split())
dp = [0] * (k+1)
worth=[]  # 주어진 동전들 각각의 가치
for i in range(n):
  worth.append(int(input()))

dp[0]=1		# 동전 1개만 쓰는 경우를 위해 1로 선언
for i in worth:  # 주어진 동전 하나씩 차례대로 반복
    for j in range(i, k+1): # j는 동전들로 만들수있는 합들
        if j-i >= 0:    # 음수면 합보다 동전 하나의 가치가 더 큰것
            dp[j] += dp[j-i]


print(dp[k])

좋은 웹페이지 즐겨찾기