[백준 2294] 동전2

🍎 [백준 2294] 동전2

문제 링크

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

 

⚾ 코드

코드 1

n, k = map(int, input().split())
dp = [100001]*100001
coins = [int(input()) for _ in range(n)]
coins.sort()

for coin in coins:
    for now in range(1, k+1):
        if now % coin != 0:
            dp[now] = min(dp[now], dp[now-coin]+1)
        else:
            dp[now] = min(dp[now], now//coin)

if dp[k] == 100001:
    print(-1)
else:
    print(dp[k])

 

코드 2

n, k = map(int, input().split())
dp = [100001]*100001
coins = [int(input()) for _ in range(n)]

dp[0] = 0

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

if dp[k] == 100001:
    print(-1)
else:
    print(dp[k])

 

🔔 해결 과정 & 깨달은 점

- 이 문제는 그리디 기법으로 풀 수 있는 거스름 돈 문제와 거의 동일하지만 화폐 단위에서 큰 단위가 작은 단위의 배수가 아니기 때문에 그리디 기법이 아닌 다이나믹 프로그래밍 기법으로 풀어야 했다.

- 처음에는 코드1의 방법으로 풀었다. coin을 나누어서 0이 나오는 경우와 그렇지 않은 경우를 나눠서 풀고, 0이 나오지 않으면 dp[now-coin] + 1과 dp[now]의 값을 비교했다.

 

이렇게 진행하니 문제점이 있었다. 바로 coin이 정렬 되지 않은 상태로 들어오면 오류가 나는 것이다.

예를 들어

3 12
10
4
2

 

이런 입력이 들어오면 답은 (10 + 2) 의 2 개가 나와야 한다.

그러나 정렬을 하지 않으면 코드1의 방법으로는 (4+4+4)의 3개가 나온다.

따라서 코드1의 방법에는 sort() 과정이 꼭 필요한 것이다.

 

제출하니 맞긴 했지만, 이 과정을 하지 않아도 되는 방법이 있을 것 같았다.

내가 푼 방법은 완성되지 않은 다이나믹 프로그래밍 기법 같이 느껴졌다.

 

이것이 취업을 위한 코딩 테스트다 with 파이썬 책에 비슷한 문제가 있어 풀이를 참고했다.

그 방법을 반영한 것이 바로 코드2이다.

 

내가 구현한 방법과 비슷하지만, dp[0] = 0으로 초기화해두고 시작하는 것이 달랐다.

 

그리고 내가 간과 한 것이, 

12//3 = 4, 12%3 == 0 과 12 = (3-3-3-3)은 같다는 것이다.

 

나는 bottom-up 방법으로 풀기 때문에 굳이 나누기를 한 값이 0인지 확인하는 과정은 필요 없었다.

 

따라서 코드2의 방법은 내가 기존에 작성한 코드1보다 훨씬 간결해졌다.

 

다이나믹 프로그래밍 기법을 활용한 문제를 조금 더 연습해보아야겠다.