[인프런] 동전 바꿔주기

---

문제설명

명보네 동네 가게의 현금 출납기에는 k가지 동전이 각각 $n_1, n_2, ..., n_k$개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꾸어 주려고 한다. 이 때, 동전 교환 방법은 여러가지가 있을 수 있다. 예를 들어, 10원, 5원, 1원 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.

• 20 = 10원 x 2개
• 20 = 10원 x 1개 + 5원 x 2개
• 20 = 10원 x 1개 + 5원 x 1개 + 1원 x 5개
• 20 = 5원 x 3개 + 1원 x 5개

입력으로 지폐의 금액 T, 동전의 가지수 k, 각 동전 하나의 금액 $p_i$와 개수 $n_i$가 주어질때 지폐를 동전으로 교환하는 방법의 가지 수를 계산해라. 방법의 수는 $2^{31}$를 초과하지 않는 것으로 가정한다.

입력조건

• 첫줄에는 지폐의 금액 T(0 <= T <= 10,000), 둘째 줄에는 동전의 가지수 k(0 <= k <=10)이 주어진다.
• 셋째줄부터 마지막 줄까지는 각 줄에 동전의 금액 $p_i$(0 < $p_i$ <= T)와 $n_i$(0 <= $n_i$ <= 10)이 주어진다. $p_i$와 $n_i$사이에는 빈 칸이 하나씩 있다.

출력조건

• 첫 줄에 동전 교환 방법의 가지 수를 출력한다.(교환할 수 없는 경우는 존재하지 않는다.)

사고과정

• 처음에 상태트리를 만들때, 갈래를 각 동전 사용하는 경우에 따라 가지를 뻗어나가도록 했다. 이렇게 DFS를 구현했지만, 중복되는 경우를 제거하지 못했다.. 집합자료구조로 받았지만 시간초과가 발생.. 중복되는 경우를 탐색하는 데 시간이 초과된다..
• 강의를 보니, 상태트리 가지를 뻗어나갈 때, 해당 동전을 몇개 사용하는지에 따라 나누었다..아차 싶었다..
• 상태트리의 레벨을 주어진 동전의 인덱스로 설정하고, 해당 인덱스의 동전을 주어진 해당 동전의 개수 즉, 0개부터 $n_i$개까지의 for loop를 DFS 함수 안에 서 돈다.. 그리고 누적합이 목표 금액 T보다 커지게 되면 바로 탐색을 중단하는 cut-edge도 포함시켜야 시간초과가 발생하지 않는다.
• 아이디어만 듣고 소스코드로 구현하는 데는 어렵지 않았다.. 흐..상태트리를 만드는 아이디어를 생각해내기 쉽지 않다.. 

풀이(스스로 못 푼 풀이)

- 나의 풀이

T = int(input())
k = int(input())
p, n = [], []
for _ in range(k):
    price, cnt = map(int, input().split())
    p.append(price)
    n.append(cnt)
answer = 0

def dfs(L, sum_val):
    global answer
    if sum_val == T:
        answer += 1
        return
    elif L == k:
        return
    else:
        for i in range(0, n[L]+1):
            # cut-edge
            if sum_val + (i * p[L]) <= T:
                dfs(L+1, sum_val + (i * p[L]))

dfs(L=0, sum_val=0)  # 동전의 idx, 누적합
print(answer)

- 강의 풀이

T = int(input())
k = int(input())
cv, cn = [], []
for _ in range(k):
    a, b = map(int, input().split())
    cv.append(a)
    cn.append(b)
cnt = 0


def DFS(L, sum):
    global cnt
    if sum > T:
        return
    if L == k:
        if sum == T:
            cnt += 1
    else:
        for i in range(cn[L]+1):
            DFS(L+1, sum + (cv[L] * i))


DFS(L=0, sum=0)
print(cnt)