220224 - 동전 1

◾ 동전 1 : 백준 2293번

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

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

• 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

• 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

입출력 예

◾ 풀이

1. 해설

• 동적 계획법을 통해 1부터 k까지 경우의 수를 구해간다.
  • i : 현재 구하려는 수, k : 목표 수
  • dp[i] = dp[i-num_1..num_n]
  • num을 기준으로 1부터 k까지 반복하여야 동전의 구성이 같은 경우를 배제할 수 있다.

2. 프로그램

1. n, k, num_list 입력
2. dp 초기화(dp[0] = 1)
3. num_list를 기준으로 1..k까지 반복하며 계산
4. dp[k] 반환

# 코드

# 입력
n, k = map(int, input().split(' '))
num_list = [int(input()) for _ in range(n)]

# dp 초기화
dp = [0] * (k + 1)
dp[0] = 1

# num_list 기준 반복
for num in num_list:
    # 1..k까지 가능한 경우 확인
    for i in range(1, k+1):
        if i >= num:
            dp[i] += dp[i - num]

# dp[k] 반환

print(dp[k])

• Input
  3 10
  1
  2
  5

• 오류 코드
  • 1..k 반복, num_list 반복의 위치 변경만으로 해결할 수 있는 문제
  • 동일한 구성의 반복을 피하기 위해 num_list 반복을 상위로 두어야 해결 가능

# 모든 경우를 반복하므로 동일하지만 숫자의 순서가 다른 경우도 더해진다.
for i in range(1, k+1):
    for num in num_list:
        if i >= num:
            dp[i] += dp[i - num]