[BOJ] 13902 개업 2 (Python3)

문제

해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나 해빈이는 낭비를 매우 싫어하기 때문에 요리 할 때, 필요 이상 크기의 웍을 사용하지 않으며, 주문 받은 짜장면의 그릇 수에 딱 맞게 요리한다.

예를 들어 짜장면 4그릇을 주문 받았는데 5그릇 이상을 요리하지 않으며, 4그릇을 요리할 수 있는 웍에 3그릇 이하의 요리를 하지 않는다.

해빈이가 5그릇을 주문 받았고, 해빈이가 가지고 있는 웍의 종류가 1, 3그릇 용이라면 처음에 1,3그릇용 웍을 동시에 이용하여 4그릇을 만들고 다음 1그릇용 웍을 이용하여 1그릇을 만들어 총 5그릇을 두 번의 요리로 만들 수 있다.

해빈이가 주문 받은 짜장면의 수와 가지고 있는 웍의 크기가 주어질 때, 최소 몇 번의 요리로 모든 주문을 처리할 수 있는지 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 해빈이가 주문 받은 짜장면의 수N(1≤N≤10,000)과 가지고 있는 웍의 개수 M(1≤M≤1,000)이 주어진다. 두 번째 줄에는 웍의 크기 Si(1≤Si≤N)이 M개가 주어지며 같은 크기의 웍을 여러 개 가지고 있을 수 있다.

출력

해빈이가 모든 주문을 처리하기 위해 해야 하는 최소 요리 횟수를 출력한다. 만약 모든 주문을 처리 할 수 없는 경우 -1을 출력한다.

정답 코드

from itertools import combinations

n, m = map(int, input().split())
woks = list(map(int, input().split()))
setWoks = set(woks)

for i in range(m):
    for j in range(i + 1, m):
        setWoks.add(woks[i] + woks[j])

INF = 987654321

memo = [INF for _ in range(10001)]
memo[0] = 0

for i in range(1, n + 1):
    for wok in setWoks:
        if i - wok >= 0:  
            memo[i] = min(memo[i], memo[i - wok] + 1)
            
if memo[n] == INF:
    print(-1)
else:
    print(memo[n])

 5 2
 1 3


2

문제 풀이

이 문제는 동적계획법, 메모제이션을 이용해서 풀이한다.

n의 최댓값인 10000까지의 값이 들어올 수 있는 배열을 만들어주고, 이 배열에 메모하며 진행해간다.

이를 위해 먼저 한번에 하나의 웍만 쓴다고 바꾸어 현재 웍으로 조합가능한 웍의 크기를 경우에 수에 추가해준다.

예를들어 1, 3의 웍이 있다면 두개를 모두 사용했을때의 경우의 수는 4이므로 4도 하나의 웍으로 간주하여 요리횟수당 1, 3, 4의 크기의 웍을 골라 사용할 수 있다.

배열의 각 인덱스가 곧 현재 만든 짜장면의 개수이므로, 해당 배열 인덱스에 하나씩 접근해가며 가장 적은 횟수시도로 만들 수 있는 목표 짜장면 개수를 업데이트해가면 된다.