[17208] 카우버거 알바생

https://www.acmicpc.net/problem/17208

동적계획법으로 접근한 문제다.

---

풀이 방법

2차원 배열 dp를 생성. x열은 소유하고 있는 버거를, y행은 소유하고 있는 감자튀김이다.

따라서 dp[x][y]는 버거 x개와 감자튀김 y개를 가지고 있을 경우 받을 수 있는 최대 주문의 수를 의미한다.

 

M행 K열의 2차원배열을 생성해야 하는데, 인덱스로 접근하기 편하게 dp[M+1][K+1] 배열로 선언하였다.

 

입력된 주문이 버거 M개 혹은 감자튀김 K개를 초과한다면 해당 주문은 탐색할 필요가 없다.

 

dp[M][K]부터 dp[0][0]까지 역순으로 탐색하여 (동일 주문은 하나만 받을 수 있다.)

주문을 받지 않고 남아있는 음식을 아낄 것인지 (dp[x][y]) 혹은

해당 주문을 받을 것인지 (dp[x-현재 주문의 버거 개수][k-현재 주문의 감자튀김 개수]+1)

둘 중 더 큰 값을 선택하여 현재 탐색 중인 곳을 갱신하면 된다.

 

따라서 현재 보유 중인 버거가 x개, 감자튀김이 y개이며 현재 요청된 주문의 버거 개수가 dx, 감자튀김의 개수가 dy일 경우, 점화식은 다음과 같다.

dp[x][y] = max(dp[x-order.dx][y-order.dy]+1,dp[x][y])

---

정답 코드