[백준] 2294 동전 2 - Python (DP)

백준 로고

 

Contents

---

1. 문제 정의 및 예제 해석

(문제 링크: https://www.acmicpc.net/problem/2294)

2294번: 동전 2

입력 출력 및 예제

동전 종류 개수(n)와 만들어야 하는 금액(k)이 주어지고, 다음 n개의 줄에 걸쳐, 각각 동전의 가치가 주어집니다. k원을 만들기 위해 사용되는 최소 동전 개수를 출력해야 합니다.(불가능한 경우 -1, 각 동전은 몇 개라도 사용 가능)

3 15 : 동전 종류는 3개, 목표 금액은 15

1 : 첫 번째 동전 - 1원짜리

5 : 두 번째 동전 - 5원짜리

12 : 세 번째 동전 - 12원짜리

15원을 만들기 위해 5원을 3개 쓰는 게 최소 동전 개수이다. 그러므로 3을 출력.

 

2. 전체 코드

n,k=map(int,input().split())
coin_li=sorted([int(input()) for _ in range(n)])
dp=[10001]*(k+1)
dp[0]=0
for i in range(1,k+1):
    for c in coin_li:
        if i-c < 0:
            break
        else:
            dp[i] = min(dp[i-c]+1,dp[i])
print(-1 if dp[k]==10001 else dp[k])

 

3. 해설 

1) 입력 및 dp 리스트 생성

n,k=map(int,input().split())
coin_li=sorted([int(input()) for _ in range(n)])
dp=[10001]*(k+1)
dp[0]=0

* 코드 해설

n, k를 int로 입력받습니다. coin_li는 n번에 걸쳐 동전의 가치를 입력받아 정렬해서 저장해줍니다. 정렬하는 이유는 dp 리스트를 채울 때, if i-c <0: 인 조건문 때문입니다. 아래에서 설명하겠습니다. dp 리스트는 인덱스가 목표 동전 금액이고, 값이 그 금액을 만들기 위해 사용되는 최소 동전의 개수를 만들기 위한 리스트입니다. 10,001로 초기화하는 이유는 동전의 최소가치는 1원짜리이고, 목표 금액의 최댓값은 10,000원 이기 때문에, 이론적으로 가능한 동전의 최대 개수는 10,000개 이고, 그보다 1 큰 10,001로 초기화했습니다. 즉, dp 리스트를 매우 큰 값으로 초기화함으로써, dp 리스트를 채워나갈 때 min() 연산으로 최솟값을 저장할 수 있습니다. dp[0]은 0원을 만들 때 필요한 최소 동전의 개수를 저장하며, 0으로 초기화해줍니다. 

 

 

2) 핵심 알고리즘 (dp 채우기)

for i in range(1,k+1):
    for c in coin_li:
        if i-c < 0:
            break
        else:
            dp[i] = min(dp[i-c]+1,dp[i])
print(-1 if dp[k]==10001 else dp[k])

* 코드 해설

1원부터 k원까지 for문을 통해 i로 반복합니다. 각 i원은 dp[i]에 i원을 만들기 위한 최소 동전 개수를 저장하는 연산을 하기 위한 것입니다. 각 i에 대해, coin_li를 순차적으로 반복하며, i-c < 0 인 경우(목표 금액 보다, 동전 가치(c)가 더 큰 경우) break 합니다. 여기서 coin_li를 정렬해서 사용하는 이유가 나옵니다. coin_li가 오름차순 이어야, i-c <0 일 때 break 해서, 그보다 가치가 큰 동전들은 보지 않습니다. i-c가 0 이상인 경우(else)는 dp[i] = min(dp[i-c] + 1, dp[i]) 연산을 합니다. 이는 예시와 함께 이해하는 게 좋습니다.

문제에서 준 예제를 그대로 보겠습니다. 

1. i = 1, c= 1 일 때, dp[1]에는 1원을 만들 때 필요한 최소 동전 개수를 채워야 합니다. 이때, 1원짜리 동전이 있으므로, 0원을 만들 때 필요한 최소 동전 개수 + 1(dp[i-c] + 1)을 합니다. 즉, 기존 dp[1]과 dp[0]+1 중 더 작은 값을 dp[1]에 넣습니다. 
2. i = 5, c =1 일 때, i-c가 0보다 크므로 else로 빠집니다. 이는 4원에서 1원을 더해 만드는 방법으로, dp[i-c] + 1 == dp[4]+1 입니다. min(dp[5], dp[4]+1) 중에 dp[5]는 처음 와보므로, 초기값 10,001이고 dp[4]는 4로 dp[4]+1(5)이 min에 의해 선택됩니다. dp[4]가 4인 것은, 반복해보면 그렇게 나옵니다.
3. i = 5, c = 5 일 때, i-c가 0 이므로 else로 빠지고, min(dp[0]+1, dp[5])가 연산됩니다. 위에 의해 dp[5]는 5이고 dp[0]+1은 1이므로 dp[0]+1이 min에 의해 선택됩니다. 

이런 식으로, 동전 리스트(coin_li)를 순차적으로 돌며, 목표 금액(i)-현재 동전 가치(c)가 0 이상일 때 그 인덱스를 dp에서 찾아, 최소 동전 개수라고 가정하고, min 연산으로 최솟값을 갱신시켜 나갑니다.

최종 적으로, dp[k]는 k원을 만들기 위한 최소한의 동전 개수가 저장되어 있을 텐데, 그게 불가능한 경우 초기값 10,001이 들어있게 됩니다. 그래서 삼항 연산을 이용해, dp[k]==10001 이면 -1을 출력하고, 아니면 dp[k]를 출력합니다.

(삼항 연산 개념: [Python] 삼항 연산자 (Tenary Operator))

[Python] 삼항 연산자 (Tenary Operator)

 

4. 느낀 점

dp 문제를 풀다 보면, k번째가 최솟값이라고 가정하고 k+1번째에 어떤 연산을 해야 최솟값이 되는지 연산 식을 찾음으로써, dp 리스트를 채워나가는 형식의 문제가 많습니다. 이 문제도 그 유형중 하나입니다. dp 문제는 처음에 굉장히 익숙지 않고, 이게 뭔 문제야 라는 느낌이 듭니다. 어느 정도 풀다 보면, dp 문제 만의 공식이 보이고, 적용할 수 있게 되는 것 같습니다. 

 

이번엔 DP(Dynamic Programming) 알고리즘 문제를 풀어보았습니다.

읽어주셔서 감사합니다.

다음에 더욱 유익하고 재미있는 글로 찾아오겠습니다.