[백준 2024/09/28] 9084번 동전

1. 문제

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

2. 접근 방법

이 문제를 해결하기 위해 우선 돈의 가치를 받은 후, 내림차순으로 정렬해주었다.

이를 통해 큰 값을 지닌 동전의 몫에 따라 값을 확인할 수 있도록 하였다.

차례로 몫에 따라, dfs 함수를 호출 해 주고, i == n-1이라면 마지막 동전이기 떄문에, 나머지가 0이라면 1을 return 해 주었다.

 

이후, count_coin이라는 함수를 작성하였다.

total은 남은 금액을 의미하고, i는 동전의 순서를 의미한다. c_dict는 이전에 동일하게 계산한 값이 있다면 해당 dictionary 값을 반환해 주었다.

 

c_dict[(i, total)] 을 통해서, 같은 값에 접근하게 된다면 딕셔너리 값을 반환해 주었다.

i 는 동전의 순서를 나타내고, total은 남은 금액을 나타낸다.

아래와 같은 경우엔 c_dict가 호출 되어, 이후의 계산을 할 필요가 없어질 것이다.

 

3. 코드

def count_coin(total, i, n, c_dict, coin_values):
    if total < 0:
        return 0
    if c_dict.get((i, total)):
        return c_dict[(i, total)]
    if i == n-1:
        if total % coin_values[i] == 0:
            return 1
        return 0

    sub_sum = 0
    quo = total//coin_values[i]
    for q in range(quo + 1):
        sub_sum += count_coin(total - q*coin_values[i], i+1, n, c_dict, coin_values)

    c_dict[(i, total)] = sub_sum
    return c_dict[(i, total)]


def count_coins():
    coin_num = int(input())
    coin_values = list(map(int, input().split()))
    coin_values.sort(reverse=True)
    money = int(input())
    print(count_coin(money, 0, coin_num, {}, coin_values))


if __name__ == "__main__":
    repeat = int(input())
    for _ in range(repeat):
        count_coins()

 

https://edder773.tistory.com/269

[백준 9084] 동전 (python)

 

dp로 풀 수 있는 좋은 방법이다.