백준 :: 동전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원) 갱신!
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])
Author And Source
이 문제에 관하여(백준 :: 동전1 <2293번>), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@hyebinnn/백준-동전1-2293번
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
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])
Author And Source
이 문제에 관하여(백준 :: 동전1 <2293번>), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyebinnn/백준-동전1-2293번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)