[백준 2624] 동전 바꿔주기

문제 출처 : https://www.acmicpc.net/problem/2624

 

이 문제는 2002년 정보 올림피아드 중등부 2번 문제 입니다.

 

다빈치코딩 알고리즘 책에서 동전 문제들은 많이 다루었습니다.

[백준 2091] 동전 : https://wikidocs.net/265710

06. 동전 [백준 2091]

문제 이해하기

동전 문제들을 통해서 다양한 문제풀이 방법을 배웠습니다. 동전1(2293) 문제에서 경우의 수를 구하는 방법을 배웠고, 동전(2091) 문제에서 동전의 개수가 정해져 있는 문제를 풀어보았습니다. 이 문제에서 다른점은 동전의 개수를 출력하지 않아도 된다는 점입니다. 동전의 개수를 출력하지 않아도 된다는 점에서 좀 더 쉽게 문제를 해결할 수 있습니다.

동전2(2294) 문제를 풀 때 금액 t를 만들기 위해 n번째 동전을 사용하는 경우와 사용하지 않는 경우로 나누어 생각했습니다. 이 문제에서도 같은 방식으로 문제를 해결할 것입니다. 다른점은 동전 한개씩 넣는 것이 아니라 넣을 수 있는 모든 경우를 넣을 것입니다. 왜냐하면 각각의 동전이 몇 개씩 쓰였는지 알 수 없기 때문 입니다. 동전 문제처럼 각각의 동전의 개수를 관리한다면 문제 없지만 이 문제에서는 동전의 개수를 관리하는 것이 아니라 경우의 수만 구하기 때문에 동전의 개수까지 관리한다면 메모리 초과가 날 수 있습니다.

코드 작성하기

그럼 코드를 작성해 보겠습니다.

입력 받기

T = int(input())
K = int(input())

coins = [[0, 0]]
for _ in range(K):
    p, n = map(int, input().split())
    coins.append([p, n])

지폐의 금액 T와 동전의 가지수 K를 입력 받습니다. 다음으로 각각의 동전의 금액 p와 개수 n을 입력 받아 이것을 coins라는 리스트에 넣었습니다. coins에 [0, 0] 초기값으로 넣어두었습니다. k - 1번째를 사용하기 때문에 0번째인 경우 0 - 1으로 -1이 들어가게 됩니다. 리스트의 -1번째는 마지막 값이기 때문에 마지막 데이터를 가져와 문제가 생길 수 있습니다. 이런 경우를 피하기 위해 0번째를 초기에 넣어 마지막 값을 가져오는 경우가 없도록 하였습니다.

Bottom-up 구하기 1

Top-Down이 아닌 Bottom-Up으로 작성하겠습니다. Top-Down으로 구하면 시간초과가 날 수 있습니다. 실제로 Top-Down으로 작성해서 제출해 보니 시간초과가 나서 Top-Down 후 Bottom-Up으로 바꿀까 하다가 앞서 동전문제를 많이 해결해 보았으니 바로 Bottom-Up으로 작성하였습니다.

dp = [[0] * (T + 1) for _ in range(K + 1)]
dp[0][0] = 1
for k in range(1, K + 1):
    p, n = coins[k]
    for t in range(T + 1):
        for i in range(n + 1):
            if t < p * i:
                break
            dp[k][t] += dp[k - 1][t - p * i]    

print(dp[K][T])

dp라는 이차 리스트를 만들었습니다. k번째 동전까지 사용해서 금액 t를 만들 때의 경우의 수를 저장해 놓을 것입니다. 먼저 dp[0][0] 을 1로 초기화 하였습니다. 동전 아무것도 사용하지 않고 0원을 만드는 것도 하나의 방법이기 때문 입니다.

이제 T원을 만들기 위해서 모든 경우의 수를 파악합니다. k번째 동전을 0개부터 n개까지 사용한 모든 경우를 더해주는 것입니다. 0개부터 시작하는 이유는 k - 1번째 동전까지 사용해서 t원을 만드는 경우입니다. 이전 동전문제들에서 동전을 사용하지 않는 경우와 사용하는 경우만 있었다면 이 문제에서는 동전을 사용하지 않는 경우부터 n개까지 사용한 모든 경우를 더하는 것입니다.

p * i 가 t보다 큰 경우는 t - p * i 값이 0보다 작다는 뜻입니다. 합계가 0보다 작은 경우가 없다면 i값이 더 커져도 합계는 무조건 마이너스 값이기 때문에 continue가 아닌break로 끝냈습니다.

출력하기

마지막으로 dp[K][T]인 K번째 동전까지 사용하여 T원을 만드는 경우의 수를 출력하면 됩니다.