[Python][백준] 2293번 동전 1

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

공부 날짜 : 2023.02.15
정답 참조 여부 : X

다양한 가치를 가진 동전을 제한없이 사용해서 k금액을 만드는 방법의 경우의 수를 묻는 문제이다.

---

DP의 Knapsack알고리즘을 활용해서 문제를 풀었다.

처음에는 조합문제기 때문에 백트래킹으로 문제에 접근했는데 시간초과가 나왔다. (왜지? 연산량 O(n*k)같은데...)

그래서 알고리즘 분류를 확인 했더니 DP문제라고 나와서 Knapsack알고리즘을 떠올렸다.

k+1의 리스트를 만들고 현재까지의 동전만 가지고 해당 가치를 만드는 방법의 경우의 수를 모두 만들었다.

그 다음 동전에서 이전 동전까지의 경우의 수를 참고하여 경우의 수를 추가 해줬다.

예시로 예를 들면

0 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1

이게 1원짜리 동전으로 각 가치를 만드는 경우의 수로 1원짜리 k개 만 사용하면 되니 당연하다.

0 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1
1 1 2 2 3 3 4 4 5 5 6

이게 2원짜리 동전으로 각 가치를 만드는 경우의 수인데
1원의 가치는 만들 수 있는 방법이 없기 때문에 이전에 구한 경우의 수를 그대로 가져왔다.

그 다음은 1원짜리만으로 만드는 방법의 수 + 2원까지 사용했을때 j-k인 경우의 수인데

무슨말이냐면 5원을 만들기 위한 방법은 1원짜리만으로 만드는 방법의 수 + 2원짜리까지 사용했을때 3원을 만드는 경우의 수이다.

왜냐하면 3원짜리 만든 방법에 2원짜리 동전 하나 추가하면 되기때문

다음 과정까지 보면

0 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1
1 1 2 2 3 3 4 4 5 5 6
1 1 2 2 3 4 5 6 7 8 10

이 된다.

다시 예시를 들자면 5원짜리 써서 5원의 가치를 만드는 방법은 1,2원만 사용하여 만든 경우의 수 + 5원까지 써서 0의 가치를 만드는 경우의 수(모두 사용하지 않는 1가지 방법)의 합이 되는 것이다.

내 글로 이해가 되지 않는다면, 다른 블로그의 Knapsack포스팅 설명을 보는 것을 추천한다.난 그림을 넣지 않아서 이해하기 힘들겁니다.

소스코드

import sys
input = sys.stdin.readline
##########################################
n, k = map(int, input().split())

# 이전단계의 경우의수를 저장하는 리스트
dp = [0 for _ in range(k+1)]

for i in range(n):
    # 이번 코인가치에 따른 경우의 수를 저장하는 리스트
    new_arr = [0 for _ in range(k+1)]
    coin_cost = int(input())
    # 만약 코인의 가치가 k보다 크면 고려할 필요 없음
    if coin_cost > k:
        continue

    # 코인 가치보다 작은 수는 이전까지 경우의수 그대로 가져감
    for j in range(coin_cost):
        new_arr[j] = dp[j]

    # 0가치는 모두 0개 넣으면 되니까 1로 통일됨
    new_arr[0] = 1

    # 경우의 수는 이번 코인을 사용하지 않는 경우의수(dp[j]) 와
    # 이번 코인을 포함해서 k-cost의 경우의 수(new_arr[j-coin_cost] 의 합
    # 두번째 경우의 수는 k-cost에서 cost동전 하나만 추가된 케이스
    for j in range(coin_cost, k+1):
        new_arr[j] = dp[j] + new_arr[j-coin_cost]

    dp = new_arr.copy()


print(new_arr[k])