[PYTHON] 백준 2294 - 동전 2

성능 요약

메모리: 116580 KB, 시간: 156 ms

분류

다이나믹 프로그래밍

문제 설명

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

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

입력

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

출력

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

---

아이디어, 문제풀이

• 큰 수부터 차례대로 넣어보며, bfs를 활용할 수 있는 방법으로 queue를 활용한다.
• 최소개수의 출력이므로, 방식을 생각해줘야 한다.

---

TROUBLE SHOOTING

• 이 문제가 잔인한 이유는, dp 로 풀면 저어엉말 훨 씬 쉽 게 풀 수 있다는점이다. 그래도 양옆을 가린 치타처럼… bfs로 풀어보자.

• 입력값을 통해 강제로 total, count를 만들어야 하는 과정이 정말 힘들었다. 그래도, 이 문제를 통해 어느정도 bfs를 구현할때에 어느정도 감이 잡힌것 같아 다행이라 생각했다. 계속 deque의 내용이 어떻게 바뀌는지를 확인하며 구현한 문제는 이 문제가 처음이였는데, 생각보다 유용했고, 앞으로도 자주 활용하게 될것같다.

• 의외로 변수명을 정해주는 부분이 좀 어려웠는데, 내가 직접 배열을 재가공해서 얻어내고, 그 배열에 두가지 특성을 부여해서 활용해야 하다보니, for문과 if문의 조건을 잡아줄 때 많이 힘들었던것 같다.

• 가장 어려웠던건 visit에 대한 부분 이였는데, 앞으로 나는 value체크를 할때 false, true가 아닌 1, 0 으로만 진행할것을 맹세 한다. 후에 여러 코드들을 참고 했는데, 나는 그 어떤 방식들보다 0, 1, 더 나아가서 -1로만 체크하는게 가장 편한것 같다.
  이 문제는 visit을 통해 중복되는 값들을 제외해주지 않으면 이 문제는 시간 초과가 났었다. 덕분에 visit의 선언, visit의 특성에 대해서 많은 시간을 투자해 공부할 수 있었다. 깊게 해매면서 마주했던 정보들도 꽤 많았는데, visit을 set()을 통해 집합으로 정했을때도 문제가 풀렸다.

  ```python
  def bfs(graph, start, k):
      
      #visit 관련해서 초기화(중복여부에 대한 체크)
      visit = [0] * (k+1)
      que = deque()
      que.append(start)
  
      while que:
          
          total, count = que.popleft()
  
          if total == k:
              return count
  
          for i in range(len(graph)):
              coin = graph[i]
              sum = total + coin
  
              if sum <= k and visit[sum] == 0:
                  # count += 1
                  visit[sum] = 1
                  que.append([sum,count + 1])
  
              elif sum > k:
                   continue
  ```
  
  que.append([sum,count + 1]) 앞으로의 출력값들도 이런식으로 설계해야 하는데… 잘 떠올릴 수 있을지 아직은 확신이 서지 않는다 ;ㅁ;

---

코드

#https://www.acmicpc.net/problem/2294
#동전 2
#2294

from collections import deque
# import sys
# input = sys.stdin.readline

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

graph = []

for _ in range(n):
    a = int(input())
    graph.append(a)

graph = sorted(list(set(graph)), reverse=True)

# print(graph)

def bfs(graph, start, k):
    
    #visit 관련해서 초기화(중복여부에 대한 체크)
    visit = [0] * (k+1)
    que = deque()
    que.append(start)

    while que:
        
        total, count = que.popleft()

        if total == k:
            return count

        for i in range(len(graph)):
            coin = graph[i]
            sum = total + coin

            if sum <= k and visit[sum] == 0:
                # count += 1
                visit[sum] = 1
                que.append([sum,count + 1])

            elif sum > k:
                 continue

        # for i in range(len(graph)):
        #     coin = graph[i]

        #     if total + coin <= k and total + coin not in visit:
        #         # count += 1
        #         sum = total + coin
        #         visit.append(sum)
        #         que.append([sum,count + 1])

        #     if sum + coin >= k:
        #         continue

        # print(que)
        
    return -1

print(bfs(graph, [0,0], k))