파이썬 백준 2294 동전 2

import sys input = sys.stdin.readline C = [] n, k = map(int, input().split()) for i in range(n) :     C.append(int(input())) count = [0 for i in range(k + 1)] for now in range(1, k + 1) :      before = []     for coin in C :          if coin <= now and count[now - coin] != -1 :              before.append(count[now - coin])     if not before :          count[now] = -1     else:         count[now] = min(before) + 1 print(count[k])

BFS를 쓰는 문제도 아닌것같고 어려운 문제도 아닌것같은데 BFS 태그의 상 난이도로 설정을 하셨길래 일단 BFS로 구현은 했었다. 근데 제출해보니 메모리 초과...

최대한 메모리를 줄여봐도 아주 작은 코인 여러개와 최댓값의 k를 줬을 때 큐가 터무니없이 쌓이는건 답이 없는데다가, 메모리를 절약하기 위해 BFS 안에 거름망을 추가할수록 느려지는데 추가시간도 없어서 결국 점화식으로 풀었다.

 

값 k를 만들기 위한 필요갯수는 k-c를 만들기 위한(c는 동전중 아무거나 하나) 동전갯수 + 1개이다.

즉 k 이전 값들의 최소필요갯수를 알때 k-c 중 최소인 것 + 1을 k의 최소필요갯수로 만들 수 있다.

count를 기록할 리스트를 만들고 for문으로 [0]부터 채워가서 [k]까지 계산하여 출력하면 된다.