본문 바로가기
알고리즘 풀이/백준

[백준 9084] 동전 (python)

by char_lie 2023. 6. 8.
반응형

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

 

9084번: 동전

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는

www.acmicpc.net

동전 문제

동전의 종류가 주어 질 때 주어진 금액을 만드는 모든 방법의 수를 세는 프로그램을 작성하는 문제

 

사용 알고리즘

#다이나믹 프로그래밍

 

📌문제 접근 포인트

1. 동전의 종류가 오름차순으로 주어진다. 해당 동전들로 주어진 금액을 만들어보자.
2. 단순하게 다이나믹 프로그래밍을 구상해보자. 먼저 dp를 구상할때 0원으로 만들 수 있는 경우의 수는 무조건 1이므로 dp[0] = 1이다.
3. 예시를 생각해보자.
2원, 5원 동전으로 10원을 만든다고 가정해보자.
1) 2원만 사용했을 경우, 만들 수 있는 가지 수의 조합은 아래와 같은 표로 작성할 수 있다.

2) 여기서 2원과 5원의 조합으로 만들 수 있는 표를 만들면 다음과 같다.

5원을 사용할 때는, 2원의 상태를 기본베이스로 사용해서 추가를 해야한다. (경우의 수에 포함이 되어있으니)
2원과 5원이 있을 때는 7원(2+5)과, 9원(2+2+5)도 만들 수 있는 경우의 수가 생긴다.

7원을 만들기 위한 경우의 수를 구하기 위해서는 우선 앞에서 2원을 만들 수 있는 경우의 수 dp[2]와 동일하게 구조가 이루어 진다. 이는 dp[(7원 - 5원)]의 위치와 동일하다. 
9원을 만들기 위한 경우의 수를 구하기 위해서는 4원을 만들 수 있는 경우의 수 dp[4]와 동일하게 구조가 이루어진다. 이는 dp[(9원 -5원)]의 위치와 동일하다.
→ 즉, 만들고 싶은 금액을 money라 하면  dp[moeny] = dp[money-coin]의 구조이다. 

위 경우를 보면 현재 동전의 가치가 큰 금액을 만들 경우(money >= coin) 동전의 조합으로 이루어짐을 알 수 있다.
이 방법들을 활용해서 구성해보자.
4. 위 예시에서 만든 구조를 그대로 코드화 하면 성공

⚙ 내가 푼 정답 코드

import sys
T = int(sys.stdin.readline())
for _ in range(T):
    N, coins, M = int(sys.stdin.readline()), list(map(int, sys.stdin.readline().split())), int(sys.stdin.readline())
    dp = [0]*(M+1)
    dp[0] = 1 # 0원으로 만드는 가지 수 1개
    for coin in coins:
        for money in range(M+1):
            if money >= coin: # 금액이 동전의 가치보다 크면
                dp[money] += dp[money-coin] # 해당 dp는 금액 - 동전에 해당하는 dp합
    print(dp[M])
반응형

'알고리즘 풀이 > 백준' 카테고리의 다른 글

[백준 1967] 트리의 지름(python)  (0) 2023.06.14
[백준 18870] 좌표 압축(Java)  (0) 2023.06.08
[백준 1463] 1로 만들기 (python)  (0) 2023.06.05
[백준 9251] LCS (python)  (0) 2023.06.03
[백준 17298] 오큰수 (python)  (0) 2023.05.31

댓글