백준 9084 동전 / python

문제 : 9084

풀이 point

백준 2293 문제와 알고리즘이 동일하다.

굉장히 잘 설명한 블로그도 따로 있으니 이해가 안간다면 참고.

경우의 수를 구하기 위해서는 x번째 동전과 x-1번째 동전의 경우의 수를 고려할 필요가 있다.
1
2
5
라고 했을 때

10을 만들기 위한 경우의 수를 동전 1로만 만든다고 가정하자.

1만 사용
1 1 1 1 1 1 1 1 1 1

1, 2 사용
1 1 1 1 1 1 1 1 1 1
1 2 1 3 .......

여기서 4를 만들기 위한 과정을 보자. 4를 만든 경우의 수는 동전 2까지 고려했을 때 3개이다.

1+1+1+1, 1+2+1, 2+2

이 값은 어떻게 나온 것일까? 바로 동전2가 2를 만들기 위한 경우의 수 + 동전1이 2를 만들기 위한 경우의 수를 합친 것이다.

왜냐면 경우의 수란, 동전이 하나 더 고려됐을 때 증가하는 것이기 때문이다. 즉, 동전 1만 가지고는 어떤 숫자를 만들든 경우의 수 개수가 증가하지 않지만, 다른 동전이 고려될 때마다 그 동전이 활용되는 경우의 수도 세어주어야하기 때문에 그때 증가하게 된다. (ex. 1+1+1+1, 1+2+1, 2+2)

그러므로 동전을 하나만 고려할 때 (ex. 1 or 2)는 변화가 없지만 (ex. 동전 2만 고려할 때 2를 만들든 4를 만들든 경우의 수는 둘이 똑같다.) 여러 개의 동전을 고려할 때는 경우의 수가 증가한다는 것이다.

결론
1부터 x번째까지 동전을 활용하여 K만큼의 값을 만들기 위한 경우의 수를 세기 위해서는 K-(동전 x의 값어치)의 경우의 수 + 1부터 x-1번째 동전이 K를 만들기 위한 경우의 수를 합쳐야한다.

말이 길었지만 점화식으로 풀면 다음과 같다.

dp[i][j] += dp[i][j-coins[i-1]]

'''
1만 사용
1 1 1 1 1 1 1 1 1 1

1, 2 사용
1 1 1 1 1 1 1 1 1 1
1 2 1 3 .......
'''

dp는 2차원이 아닌 1차원으로도 가능하다. 그 이유는 K를 만들기 위한 X-1 동전까지 사용한 경우의 수가 무조건 포함이 되기 때문에 굳이 2차원으로 테이블을 만들어 동전이 몇번째까지 활용되었는지를 따로 저장할 필요가 없다.

풀이 코드

for _ in range(int(input())):
  N = int(input())
  coins = list(map(int, input().split()))
  K = int(input())

  dp = [[0]*(K+1) for _ in range(N+1)]

  for i in range(N+1):
    dp[i][0] = 1

  for i in range(1, N+1):
    for j in range(1, K+1):
      dp[i][j] = dp[i-1][j]
      if j-coins[i-1] >= 0:
        dp[i][j] += dp[i][j-coins[i-1]]

  print(dp[N][K])

1차원

for i in range(1, N+1):
  for j in range(coins[i-1], K+1):
      dp[j] += dp[j-coins[i-1]]