안녕하세요,
재재입니다.
boj 10982 행운쿠키 제작소 문제에 대한 솔루션입니다.
BOJ 10982 행운 쿠키 제작소
(1) 문제 설명
분류 : dynamic programming
출처 : https://www.acmicpc.net/problem/10982
테스트 케이스가 주어집니다.
그리고, (1000 이하) N개의 반죽 갯수가 주어집니다.
2개의 오븐에서 각각 반죽을 구워야하는데,
N개의 줄에 각각 오븐1 에서 구워지는 데 걸리는 시간과,
오븐2에서 구워지는 데 걸리는 시간이 들어옵니다.
최소한의 시간을 사용해서 모든 반죽을 구워야합니다.
(2) 풀이 도출
하나의 오븐에서만 구웠을 때 나올 수 있는 시간의 최댓값은 10만,
무언가 나올 수 있는 모든 상태를 표현 할 수 있을 것 같은 기분이 들었습니다.
단순히 생각하면 나올 수 있는 경우의 수는,
$$ 2^N $$
하지만, 표현 할 수 있는 상태는 최대 10만이기 때문에,
모든 상태공간을 표현하는데에는 10만의 공간만 필요합니다.
dp[i][A] : i번째 순간에 오븐 1에서 A시간만큼 일을 했을 때,
오븐 2에서 한 일의 시간의 최적값
순서는 사실 임의대로 정해도 되기 때문에,
우리는 토글을 사용해서 정확히 2가지 상태만 있어도 충분합니다.
(3) 정답 코드
BOJ 10982 행운쿠키 제작소