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

발생한 문제

동전의 순서에 따라 중복되는 경우를 빼줘야하는 문제가 발생했다.
예를 들어, 2,3,5원이 있을 때
2+3과 3+2가 같은 금액이라 중복이 안되게 제외해야 했다.
이 중복은 의도적으로 동전의 경우의 수를 계산하는 순서를 줘서
2+3은 카운트하지만, 3+2는 카운트하지 않도록 바꿨다.

풀이 아이디어

DP(Dynamic Programming)을 사용해서 풀었다.
목표 합계 금액인 m원이 있을 때
array 리스트에 0~m원까지 인덱스가 있도록 array=[0]*(m+1)으로
배열을 선언하고

1) 예제 입력의 2,3,5원에서 순서대로 꺼내어서
"for coin in coins:"

2) 인덱스에 기존 경우의 수를 더해주는 방식으로 계산을 했다.
array[i] += array[i-coin]

예시) 2,3,5원이 있다면
coins = [2,3,5] 일때
array[0]=1이고 꺼낸 동전이 coin이라면

1. 2원만 있을 때 경우의 수를 array에 저장한다.
2. 2,3원만 있다고 가정하고 기존 결과에 3원일 때의 경우의 수를 더한다.
3. 2,3,5원 있다고 가정하고 기존 결과에 5원일 때 생기는 경우의 수를 더한다.

풀이 코드

import sys
input = sys.stdin.readline
t = int(input())
dic = [0]*10001


for _ in range(t):
    # 0부터 m까지의 인덱스를 가진 배열을 선언한다.
    n = int(input())
    coins = list(map(int,input().split()))
    m = int(input())

    # 화폐의 가치를 배열로 선언 
    array = [0]*(m+1)
    array[0] = 1

    # 작은 동전부터 순서대로 경우의 수를 계산
    for coin in coins:
        for i in range(coin, m+1):
            array[i] += array[i-coin]
    print(array[m])