문제
명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.
20 = 10×2
20 = 10×1 + 5×2
20 = 10×1 + 5×1 + 1×5
20 = 5×3 + 1×5
입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오. 방법의 수는 231-1을 초과 하지 않는 것으로 가정한다.
풀이
- 테이블 정의
dp[i] = 주어진 동전으로 i를 만들 수 있는 경우의 수 - 초기값 dp[0] = 1
0을 만들 수 있는 경우의 수는 아무것도 선택하지 않는 방법이 있다.
주어진 지폐금액 T부터 0까지 순회하면서 현재 조회하고 있는 인덱스 값(금액)에서 동전의 갯수로 만들 수 있는 값들을 빼주면서 값을 업데이트해준다.
예제로 예를 들면 처음 들어오는 5는 인덱스 15부터 값이 생기기 시작할텐데 dp[15 - 5 * 1] , dp[15 - 5 * 2], dp[15 - 5*3] 이렇게 세번의 연산을 통해서 dp[0]의 값을 더하게 되고 마찬가지로 인덱스 10, 인덱스 5에도 1이 생기게 된다.
다음으로 10은 20 인덱스에서 10, 0 에 있는 값을 더해 2가 될 것이고 각각 15 10에서 또 2가 된다.
이렇게 반복해서 동전들의 갯수로 만들 수 있는 금액의 갯수가 각 dp인덱스로 담기게 되고 마지막으로 dp[T]를 프린트해주면 원하는 값을 구할 수 있다.
T = int(input())
K = int(input())
dp = [0] * (T+1)
dp[0] = 1
for _ in range(K):
penny, penny_cnt = map(int, input().split())
for i in range(T, -1, -1):
j = 1
while j <= penny_cnt and i - penny * j >= 0:
dp[i] += dp[i- penny * j]
j+=1
print(dp[T])피드백
아직도 dp문제를 보면 덜컥 겁이 나는게 있다. 엄청나게 효율적인 코드를 찾기 보다는 하나씩 돌려가면서 규칙을 찾고 그 규칙에 맞게 푸는 것이 더 나아보인다. 겉멋을 빼자.
