백준 10982번 행운쿠키 제작소

문제

데브베이커리에서는 기념일을 맞아 직원들에게 행운쿠키를 선물하기로 하였다. 회사의 간식을 담당하는 철수는 나누어줄 행운 쿠키를 준비하는 역할을 맡게 되었다. 행운쿠키를 만들기 위해서는 N개의 행운반죽을 2개의 오븐을 이용해 구워야 한다. 각각의 행운반죽은 2개의 오븐 중 1개의 오븐에서만 구워져야 하며, 어떤 오븐에서 굽는지에 따라 구워지는데 걸리는 시간이 다르다. 각각의 오븐은 독립적으로 반죽을 구울 수 있으며, 오븐에 반죽을 넣거나 빼는데 걸리는 시간은 없다고 가정하자.

철수는 행운반죽을 모두 구워야 퇴근을 할 수 있다고 한다. 철수가 최대한 빨리 퇴근을 할 수 있도록 행운반죽을 모두 굽는데 걸리는 최소 시간을 구해주자. 

문제풀이

사용한 알고리즘 : DP 

(1) 코드 8~9

 두 오븐을 A, B 라 이름 붙이겠습니다.

 'dp[i][x] : i번째 반죽, A가 x만큼 일을 할 때, B가 일하게 되는 최소 일' 이라고 설정했습니다.

 이때 100개의 일을 모두 배열로 잡으면 메모리 초과가 됩니다. 

 ( dp[100][100001] 로 잡으면 터짐 )

 잘 생각해보면, i : 0->100 을 탐색할 때, 각 탐색은 바로 이전 값으로만 최신화 됩니다.

 따라서 dp[2][100001] 로만 잡아주어도 dp 값을 최신화해 나아갈 수 있습니다.

(2) 코드 22~38

 모든 일을 A가 한다고 생각하고, A가 하는 모든 일의 양을 sum이라 하겠습니다.

 이후 0번째 ~ N-1번째 일을 차례로 탐색하면서, 일을 B가 맡는 경우 dp를 최신화 합니다.

 탐색이 끝난 후, dp[N-1][x]가 나타내는 것은, A가 x만큼 일할 때 B가 하게되는 최소 일 이겠습니다.

 따라서 모든 x에 대해 (x + dp[N-1][x]) 중 가장 작은 값이 답이 됩니다.