[DP, BFS] 백준 2294번 동전 2 with Python3

illustrated  by  あすてろid  https://www.pixiv.net/users/2033916

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

2294번: 동전 2

문제

 

정답 풀이

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
# 동전 개수 n, 목표 금액 k원

coin = []

dp = [0 for i in range(k+1)]
for i in range(n):
    coin.append(int(input()))

for i in range(1, k+1):
    # k원까지의 각 금액들 i

    a = []

    for j in coin:
        if j <= i and dp[i-j] != -1:
            # 1. coin이 목표금액 i보다 작고
            # 2. dp[i-j] 에 저장된 값이 -1이 아니라면

            a.append(dp[i-j])
# dp[i-j] 의 값은 현재 금액에서  coin j를 뺏을때의 금액을 만드는 최소 개수이다.
# ex) k = 2, j = 2. dp[2-2] = dp[0] = 0 / 그럼 0을 a에 append함.

    # 어떤 코인으로도 i원을 만들 수 없다면
    if not a:
        dp[i] = -1
    # 만들수 있다면
    else:
        dp[i] = min(a) + 1

# min(a)의 이유 : a에는 현재 목표 원 i에, j in coin으로 뺀 목표-j를 만들기 위한 최소 동전 개수가 저장되어있다.
# 그곳에서 최소값을 선택하고
# ex) coin =[1,5,12] / i = 14 / i-1 = 13, i-5 = 9, i-12= 2 /
# -> 13 은 5 2개, 1, 3개 총 5개/ 9는 5 1개 , 1 4개 총 5개/ 2는 1 2개. 총 두개
# min(a) = 2  거기에 지금 뺀 동전 개수인 1을 더해서 dp[i] 에 저장
# -> dp[14] = dp[2] + 1 = 3 ㅇㅋ?

print(dp[k])

출처:https://pacific-ocean.tistory.com/203

 

해석

dp를 아직 배우지 않은 상태로 bfs 문제라 생각해서 접근하려하니 아예 감도 오지 않아서 정답을 봤다.

 

dp가 아직 무엇인지 이 문제 만으론 알 수 없지만, 이전 단계를 활용해서 모든 경우마다 연산하지 않는 효율성이 눈에 띈다. 

 

 

이것은 출처에서 퍼온 해설이다.

3 15

1

5

12

 

위와같이 입력을 받았다고 해자.

1부터 15까지의 경우의 수를 담는 dp를 만들어준다.

아래는 1부터 15까지 필요한 동전의 개수를 최소로 나타낸 것이다.

 

i    coin

0 - 0

1 - 1
2 - 1, 1
3 - 1, 1, 1
4 - 1, 1, 1, 1
5 - 5
6 - 5, 1
7 - 5, 1, 1
8 - 5, 1, 1, 1
9 - 5, 1, 1, 1, 1
10 - 5, 5
11 - 5, 5, 1
12 - 12
13 - 12, 1
14 - 12, 1, 1
15 - 5, 5, 5

 

dp의 점화식은 dp[i] = min( dp[i - coin] ) + 1 이 될 수 있다.

 

즉 dp[i] 에는 dp[i - 1],  dp[i - 5],  dp[i - 12] 중 가장 작은 값에 1을 더해주면 된다.

 

조건은 i 가 coin보다 크거나 같아야 하고, -1 이 아니어야 한다.

 

-1 인 경우는 만들 수 없는 경우다.

 

정답 풀이 -bfs-

아직 못찾음

출처:

 

해석