BOJ 9084 동전

LONGNEW·2021년 6월 21일
0

BOJ

목록 보기
243/333

https://www.acmicpc.net/problem/9084
시간 1초, 메모리 128MB

input :

  • T(1 ≤ T ≤ 10)
  • N(1 ≤ N ≤ 20)
  • M(1 ≤ M ≤ 10000)

output :

  • N가지 동전으로 금액 M을 만드는 모든 방법의 수

코포 문제를 보다가 냅색을 사용해야하는 경우가 발생해 복습 삼아 문제를 풀어 봤다.

동전의 종류를 입력 받기 때문에 이 경우를 다 생각해 주어야 하는데 이럴 때는 DP를 사용해 주어야 한다.

https://velog.io/@jsin2475/BOJ-2293-%EB%8F%99%EC%A0%84-1
과거 문제 중 동일한 알고리즘을 사용한 문제로 동전을 지정해 줬다는 것이 다르다.

예를 들어
2
1 2
1000
이 입력 되었을 때

연산

각 코인마다 해당하는 금액을 만들 수 있는 방법을 저장하고 있어야 한다.
이를 이용해서 내가 i원을 만들려 할 때 i - j가 존재한다면 dp[i] += dp[i - j]를 통해 누적 하여 연산하도록 한다.

import sys

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    coin = list(map(int, sys.stdin.readline().split()))
    target = int(sys.stdin.readline())
    
    ans = [0] * 10001
    ans[0] = 1

    for item in coin:
        for j in range(1, 10001):
            if j >= item:
                ans[j] += ans[j - item]

    print(ans[target])

0개의 댓글