DP 에러 찾기

동전 2 

1 초 (추가 시간 없음)

128 MB

64987

19571

13830

29.412%

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

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

입력

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

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

 

다음 코드의 문제를 알아보자.

n, k = map(int, input().split())

coin = [int(input()) for _ in range(n)]

dp = [0]*(k+1)

dp[0] = 1

for i in coin:
    for j in range(i, k+1):
        if j%i == 0: # 동전의 값과 k 값이 일치하거나 나누어 떨어지는 경우
            dp[j] = j//i
        elif j-i >= 0 and dp[j-i] != 0: # 나누어 떨어지지 않으나 주어진 동전들로 구성 가능
            if dp[j] > 0:
                dp[j] = min(dp[j], dp[j-i] + 1)
            else:
                dp[j] = dp[j-i] + 1


if dp[k] == 0:
    print(-1)
else:
    print(dp[k])

 

문제점

문제가 발생한 부분

1. 동전의 입력 순서가 정해지지 않았기 때문이다.

동전의 값이 오름차순으로 입력되지 않는다면, 첫 번째 if 문에서 동전의 최소 갯수가 아닌 나누어 떨어진 값으로 입력이 된다.

예를 들어 동전의 리스트 값이 [3, 5] 이고 n, k = (2, 15) 라면, dp[15] = 3으로 갱신되지만, 동전 값의 입력 순서가 바뀔 경우 dp[15] = 5가 된다.

2. dp 배열 선언

위 문제의 경우, 최솟값을 구하는 문제이기 때문에 dp의 초기값을 0으로 설정하기보다는 k의 최댓값보다 큰 10001로 두는 것이 좋다. 왜냐하면 dp[j] > 0 이라는 전제를 두지 않아도 되기 때문에, 불필요한 예외처리를 하지 않아도 된다.

위의 결과는 동전을 입력받은 후 오름차순으로 정렬한 뒤 그대로 진행한 코드이며, 아래의 경우 1과 2를 반영하여 수정한 코드를 테스트한 결과이다. 코드도 간결하고 시간 복잡도 면에서 효율이 좋아진 것을 볼 수 있다.

[아래 코드]

n, k = map(int, input().split())

coin = [int(input()) for _ in range(n)]


dp = [10001]*(k+1)

dp[0] = 0

for i in coin:
    for j in range(i, k+1):
        if dp[j] > 0:
            dp[j] = min(dp[j], dp[j-i] + 1)
        

if dp[k] == 10001:
    print(-1)
else:
    print(dp[k])