백준 2293 파이썬

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

2293번: 동전 1

 

 

문제 요약

주어진 N개 숫자로 이뤄진 배열의 값을 더하여, K 를 만드는 경우를 구하라 (배열의 숫자는 중복하여 더해도 된다)

 

 

 

정답 코드

N, K = map(int, input().split())

arr = []
for _ in range(N):
    arr.append(int(input()))

dp = [0] * (K + 1)
dp[0] = 1

for a in arr:
    for j in range(a, K + 1):
        dp[j] += dp[j - a]
print(dp[K])

 

 

접근방법

 

시간제한, 메모리제한이 다른 문제보다 눈에띄게 작다. 즉 무작정 반복문을 돌리는 brute force 나 greedy 로는 해결할 수 없을 것이라 생각했다.

 

배열의 수를 더하여 K 가 되는 조합은 여러가지가 나올 수 있다. 예를 들어 10을 이루는 조합 중 (5, 5)가 있다면, 주어진 수를 이용하여 5 를 만드는 방법도 여러가지 존재한다. 즉 부분 합을 이용하여 정답에 가까워 지는 방법을 이용할 수 있다.

 

10을 이루는 여러 조합을 구하기 위해선, 그 전 단계인 9, 8, 7, ... , 2, 1 을 만들 수 있는 조합의 수를 구해보자. 그리하면 우리가 구하고자 하는 10 (=K) 를 구하는데 더 수월하게 접근할 수 있다.

 

 

 

여기서 a 는 주어진 N개의 숫자를 의미한다.

a 가 1만 있을 때는, 각각의 숫자를 만드는 경우는 당연히 하나다. (모든 수를 1을 더하여 만드는 방법)

이때의 값을 dp 라는 배열에 저장 해두고, a 가 2인 경우를 보자.

a 가 2일 때 2를 만드는 방법은 dp[2]에 저장할 수 있고, 값이 2로 업데이트(1 -> 2)된 것을 확인할 수 있다. 

이런 식으로 각 배열의 값들을 업데이트해나가면, 주어진 N 개 숫자로 조합할 수 있는 경우의 수를 구할 수 있따.

 

추가 )

dp[j - a] 식을 보면, a 는 N 개의 숫자중 하나이고, j 는 a 보다 크거나 같은 숫자중 하나이다.( K 보다 작거나 같기도 함).

즉 j - a 는 0 에서부터 K - a 까지의 범위를 가지는 숫자가 된다.