[백준] 백준 python 2293번 문제 및 소스코드

1. 문제 링크

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

2. 문제 

 

3. 소스 코드 및 해설

n, k = map(int, input().split()) # 동전의 종류 개수 n, 목표 금액 k
coins = [int(input()) for _ in range(n)] # 각 동전의 가치 리스트

# 목표 금액 k를 만들 수 있는 경우의 수를 저장할 dp 배열
dp = [0] * (k + 1)
dp[0] = 1 # 0원을 만드는 방법은 1가지 (아무 동전도 사용하지 않는 경우)

# 각 동전에 대해 dp 배열을 갱신
for coin in coins:
	for j in range(coin, k + 1):
    	dp[j] += dp[j - coin]
        
# 결과 출력 : 목표 금액 k를 만들 수 있는 경우의 수
print(dp[k])

---

1) 입력 받기

n, k = map(int, input().split()) #동전의 종류 개수 n, 목표 금액 k
coins = [int(input()) for _ in range(n)] # 각 동전의 가치 리스트

- 첫 번째 줄에서 동전의 종류 n 과 목표 금액 k 를 입력받는다.
- 두 번째 줄부터 n 개의 동전 가치를 입력받아 리스트 coins에 저장한다.
 
2) DP 배열 초기화

dp = [0] * (k + 1)
dp[0] = 1 #0원을 만드는 방법은 1가지 (아무 동전도 사용하지 않는 것)

- dp 배열은 목표 금액을 만들 수 있는 경우의 수를 저장하는 배열
- dp[i]는 i원을 만들 수 있는 경우의 수
- 처음에 모든 값은 0으로 초기화도고, dp[0] = 1로 설정한다. 이는 0원을 만드는 방법은 아무 동전도 사용하지 않는 1가지 방법뿐임을 의미한다.
 
3) DP 배열 갱신

for coin in coins:
	for j in range(coin, k + 1):
    	dp[j] += dp[j - coin]

- 각 동전에 대해 반복문을 돌며, 해당 동전을 사용해서 만들 수 있는 금액을 DP 배열에서 업데이트 한다.
- dp[j] += dp[j - coin] 는 j - coin을 만들 수 있는 방법에 해당 동전을 추가해 j 원을 만들 수 있는 경우의 수를 더한다.
 
4) 결과 출력

print(dp[k])

- 최종적으로 목표 금액 k를 만들 수 있는 경우의 수를 출력한다. dp[k]에는 k원을 만들 수 있는 모든 경우의 수가 저장되어 있다. 
 

---

- 동적 프로그래밍(Dynamic Programming) 사용
- 각 금액을 만들 수 있는 경우의 수를 이전 계산 결과를 바탕으로 구하는 방식으로, 특히 배낭 문제(knapsack problem)와 유사
- 한 번 동전을 추가할 때마다 해당 금액을 만들 수 있는 경우의 수를 DP 배열에 업데이트해 나가는 방식
 
시간 복잡도 : O(n * k) 
n : 동전의 종류
k : 목표 금액