[BOJ][🟡5][백준#02294] 동전 2

문제 출처

BAEKJOON Online Judge #2294

문제

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

입력

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

출력

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

예제

입력

3 15
1
5
12

출력

3

My Sol

from collections import deque

def main():
    def BFS():
        Q = deque()
        dp = [0]*(T+1)
        for coin in coins:
            if coin > T: continue
            dp[coin] = 1
            Q.append(coin)

        while Q:
            acc = Q.popleft()
            for coin in coins:
                ssum = acc+coin
                if ssum > T: continue
                if dp[ssum]: continue
                dp[ssum] = dp[acc]+1
                Q.append(ssum)
        return dp[T] if dp[T] else -1

    N, T = map(int, input().split())
    coins = sorted(list(set([int(input()) for _ in range(N)])), reverse=True)
    return BFS()

print(main())

당연히 DP 문제일 거라고 생각했고, 문제 해결 알고리즘 제시에도 DP로 해결하라고 나와있는데, 나는 BFS를 이용해 풀었다.

나름 2,835명 중 연산시간 9등이니 그리 나쁜 코드는 아닌 것으로 보인다. (심지어 나보다 연산시간이 더 빠른 대부분의 코드들은 모두 BFS로 풀었음을 확인했다.)

1. 입력을 받고, 제시된 동전들을 set으로 중복을 제거한 뒤, list, sorted-reversed로 내림차순 정렬한다.
2. 목표값인 T보다 크지 않은 동전들 선에서 deque에 동전들을 집어넣고, 이를 확인하는 dp 배열에 표시한다.
3. 동전 크기를 내림차순 정렬해서 이전 deque에 넣은 누적 금액에 대해 동전들을 각각 대입해 카운트를 추가한다. 즉, 해당 금액을 만들기 위한 최소 동전 개수를 구할 수 있는 것이다. 이미 dp 배열에 특정 금액에 특정 값이 있다면, 그 금액을 만들기 위한 최소 개수이므로 이미 값이 있다면 넘어간다. 즉, visited의 역할을 하는 배열이다. 그런데 dp라고 이름 붙인 이유는 이전에 DP로 풀었던 기록 때문…ㅎㅎ 마찬가지로 이 과정에서 누적 금액이 T보다 크다면 분기처리해서 넘어간다.
4. 모든 순회를 마치고 dp[T]의 값을 return하는데, 이때 값이 0이면 초기값이고, 해당 누적금액을 만들 수 없다는 의미이므로 -1을 반환한다.

결과

맞았습니다!!