[Python/백준] 2293 동전 1

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

2293번: 동전 1

<문제 해설>

다이나믹 프로그래밍 문제이다. 골드인거 치고 간단하다.  다른 다이나믹 프로그래밍처럼 이전 값을 가져와서 더해주면된다. 이번엔 예시와 함께 설명하겠다.

<예시>

위 사진은 가치의 합이 k일때 가짓수를 다 적어놨다. 1일땐 1한개 2일땐 1+1,2 두개인 식이다. 여기서 규칙을 찾아낼 수 있는 데

바로 앞칸의 coin의 가치만큼 올라간값에 coin을 더해주는 방식으로 가짓수가 늘어난다는 것이다.

좀더 보기 쉽게 정리했다. 아래표는 k를 만들수있는 coin의 가짓수를 모아놨다. coin = 1은 1만을 사용해서 만드는 가짓수이고 1,2는 1과 2둘다 사용, 1,2,5는 3개를 전부다 사용한 가짓수이다. 이런식으로 모으는 이유는 중복을 피하기 위해서이다.

위표도 똑같다.  k = 6, coin = 1,2좌표의 값은 k - coin 즉 (k - coin =4, [coin =1 + coin = 2]) = 1 + 2 인 3이된다. 이런방식으로 k = 10,  coin = 1,2,3 좌표의 값은 k - coin = 5좌표의 1 + 2 + 1이된다. dp 10 의 최종 가짓수는 coin을 전부 더한 1+5+4가된다.

여기서 coin의 가치 순서를 걱정할 수 있는데 순서는 상관없다.

 

가짓수를 만드는 방식은 다더해주면 최종적으론 같기 때문이다. 이때 이런식으로 모든값을 배열을 만들어서 저장하게되면 메모리가 5MB밖에 되지 않기 때문에 초과가 생긴다. 그럼으로 값을 저장하지 않고 dp에 즉시 더하는 방식을 사용한다.

위 표를 보면 1만을 사용하는 가짓수를 coin =1 일때 더해주고 coin =2 일댄 1과 2만을 사용하는 가짓수를 더해주는 방식이다. 최종적으로 k = 10인 dp에는 10이 저장되므로 dp[k]를 출력해주면된다.

<코드>

import sys
n, k = list(map(int,sys.stdin.readline().split()))
coins = []
for i in range(n):
    coins.append(int(sys.stdin.readline()))
dp = [0]*(k+1)
dp[0] = 1

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

print(dp[k])

<코드 설명>

import sys //sys라이브러리 사용하기 위한 import
n, k = list(map(int,sys.stdin.readline().split())) //n,k값 공백을 기준으로 정수로 받아오기

coins = [] //coin값들 저장할 배열
for i in range(n):  //n만큼 반복하면서
    coins.append(int(sys.stdin.readline())) //coins에다가 coin값 넣어주기
dp = [0]*(k+1) //dp저장할 배열 생성
dp[0] = 1 // i - coin도 1개의 가짓수임으로 (ex: 5를 5로 만드는 가짓수는 1개다, i - coin  = 5 - 5)

for coin in coins: //coin을 순서대로
    for i in range(coin, k+1): //k값을 순서대로
        dp[i] += dp[i - coin] //값을 dp에 더해준다

print(dp[k]) //dp[k]를 출력해준다.