13910번: 개업
해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나
www.acmicpc.net
문제
해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나 해빈이는 낭비를 매우 싫어하기 때문에 요리 할 때, 필요 이상 크기의 웍을 사용하지 않으며, 주문 받은 짜장면의 그릇 수에 딱 맞게 요리한다.
<웍>
예를 들어 짜장면 4그릇을 주문 받았는데 5그릇 이상을 요리하지 않으며, 4그릇을 요리할 수 있는 웍에 3그릇 이하의 요리를 하지 않는다.
해빈이가 5그릇을 주문 받았고, 해빈이가 가지고 있는 웍의 종류가 1, 3그릇 용이라면 처음에 1,3그릇용 웍을 동시에 이용하여 4그릇을 만들고 다음 1그릇용 웍을 이용하여 1그릇을 만들어 총 5그릇을 두 번의 요리로 만들 수 있다.
해빈이가 주문 받은 짜장면의 수와 가지고 있는 웍의 크기가 주어질 때, 최소 몇 번의 요리로 모든 주문을 처리할 수 있는지 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 해빈이가 주문 받은 짜장면의 수N(1≤N≤10,000)과 가지고 있는 웍의 개수 M(1≤M≤100)이 주어진다. 두 번째 줄에는 웍의 크기 $S_i$(1≤$S_i$≤N)이 M개가 주어지며 같은 크기의 웍을 여러 개 가지고 있을 수 있다.
출력
해빈이가 모든 주문을 처리하기 위해 해야 하는 최소 요리 횟수를 출력한다. 만약 모든 주문을 처리 할 수 없는 경우 -1을 출력한다.
코드
from itertools import combinations
n, m = map(int, input().split())
wok = list(map(int, input().split()))
possible = set(wok)
for comb in combinations(wok, 2):
possible.add(sum(comb))
dp = [10001] * (n+1) # n그릇의 짜장면을 만들기 위해 필요한 최소 요리 횟수
dp[0] = 0
for i in range(1, n+1):
for j in possible:
if (i-j) >= 0 and dp[i-j]+1 < dp[i]:
dp[i] = dp[i-j]+1
print(dp[n] if dp[n] != 10001 else -1)
해빈이는 한 번에 최대 2개의 웍까지만 사용이 가능하다. 1개의 웍만 사용하는 경우는 입력받은 웍들의 크기 배열을 집합으로 만들어주면 되고, 2개의 웍을 사용하는 경우는 combinations 함수를 이용하여 쉽게 구할 수 있다.
dp 배열에는 n그릇의 짜장면을 만들기 위해 필요한 최소 요리 횟수가 저장된다. for문을 돌며 dp배열의 값을 채워주는데 이 때 아까 구해놓은 한 번에 가능한 그릇의 수(possible)를 이용한다. 여기서 사용되는 점화식은 다음과 같은데 이렇게 하면 Python3에서는 시간 초과가 발생해서 위의 코드와 같이 조건을 만족하는 경우에만 값을 수정하도록 하였다.
$$dp[i] = min(dp[i], dp[i-j] + 1)$$
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 17265번 나의 인생에는 수학과 함께 (0) | 2023.08.29 |
---|---|
[Python/파이썬] 백준 11909번 배열 탈출 (0) | 2023.08.24 |
[Python/파이썬] 백준 11052번 카드 구매하기 (0) | 2023.08.09 |
[Python/파이썬] 백준 2253번 점프 (0) | 2023.08.07 |
[Python/파이썬] 백준 2302번 극장 좌석 (0) | 2023.08.03 |