BOJ 13902 개업 2

항상 주어진 웍에 딱 맞게 요리해야 하고, 한 번에 두 개의 웍으로 동시에 요리가 가능하다.

주어진 양을 처리하기 위해 필요한 최소 요리 횟수를 구하는 문제이다.

같은 크기의 웍이 여러개 주어질 수도 있으므로 웍의 크기별 개수도 기록해야 할 것 같다...

일단 웍에 딱 맞게 요리해야 하므로... 느낌이 동전 문제와 비슷한 느낌이 든다.

dp...!! 그리고 생각해보면 두 개의 웍으로 동시에 요리가 가능하므로 같은 크기의 웍이 3개이상 있는 것은 의미 없다.

d[n] = 짜장면 n개 주문을 처리하기 위해 필요한 최소 요리 횟수

d[n] = min(x1, x2 가능한 모든 경우.. | d[n-x1-x2] + 1)

웍의 개수가 최대 1000개인데, 이 중 2개를 골라서 쓰는 경우와 1개만 쓰는 경우가 있는데, 1개만 쓰는 경우는 1000가지이고, 2개를 골라서 쓰는 경우는 최대 1000C2 = 1000*999/2 = 약 50만... 

n제한은 10000이기에.. 시간초과가 날 것 같다.

저 50만을 좀 줄여볼 방법으로... 1개를 골라쓰고, 2개를 골라쓰는 경우로 볼 것이 아니라 한 번에 얼마나 요리하는지로 보면 될 것 같다. (어차피 n이 1이상 10000이하이므로)

대신 미리 50만번 정도의 연산을 통해 한 번에 요리할 수 있는 양의 경우를 다 구해놓고 

d[n] = min(x의 가능한 모든 경우 | d[n-x] + 1) 이런 식으로 dp를 해보면 될 것 같다. 

AC를 받고 다른 분들의 코드를 보는데 어떤 분의 코드는 나와 방식은 비슷한데, 나처럼 미리 한 번에 요리할 수 있는 양의 경우를 다 구하는 것을 그냥 바로 d배열에 한 번에 요리할 수 있는 양의 경우x에 대해 d[x]=1로 초기화를 해주도, d[n] = min(d[n-x]+d[x]) ... 이런 식으로 구현돼있다. 결국 나랑 연산하는 수도 비슷하고 거의 똑같아 보이는데 시간차이는 꽤 많이 난다. 내 코드가 더 느리다...

이 문제는 처음 볼 때는 어려워 보였지만 dp로 접근해서 시간 초과 문제에 직면했을 때, 시간을 줄이기 위해 어떻게 해야할까 고민해서 풀었고 좋은 문제같다.