[baekjoon] 백준 2293번(파이썬): 동전 1

문제

2293번: 동전 1

알고리즘

- 반복문을 통해 코인을 확인한다.

- 반복문을 통해 코인으로 1원부터 k원까지 만들 수 있는 경우의 수를 확인한다.

- k원을 만드는 과정으로는 현재 코인 - 현재  확인 중인 수(j)의 값을 dp[j]에 더하는 방식이다.

ex) 현재 코인: 1, 2, 5일 때

index	현재 코인 : 1	현재 코인 : 2	현재 코인 : 5
1	1	0	0
2	11	dp[0] + dp[2]	0
3	111	dp[1] + dp[3]	0
4	1111	dp[2] + dp[4]	0
5	11111	dp[3] + dp[5]	dp[0] + dp[5]
6	111111	dp[4] + dp[6]	dp[1] + dp[6]
7	1111111	dp[5] + dp[7]	dp[2] + dp[7]
8	11111111	dp[6] + dp[8]	dp[3] + dp[8]
9	111111111	dp[7] + dp[9]	dp[4] + dp[9]
10	1111111111	dp[8] + dp[10]	dp[5] + dp[10]

코드

import sys


n, k = map(int, sys.stdin.readline().split())
coin = [int(sys.stdin.readline()) for _ in range(n)]
dp = [0] * 10001
dp[0] = 1

# 반복문을 통해 코인을 확인
for i in coin:
    # 반복문을 통해 코인으로 1원부터 k원까지 만들 수 있는 경우의 수를 확인
    for j in range(1, k + 1):
        if j - i >= 0:
            dp[j] += dp[j - i]
            # 1: 1
            # 2: 1 1, 2
            # 3: 1 1 1, 1 2
            # 4: 1 1 1 1, 1 1 2, 2 2
            # 5: 1 1 1 1 1, 1 1 1 2, 1 2 2, 5
            # ...

print(dp[k])

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법