[BOJ] 10777번: Greedy For Pies

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

일단 B의 파이들에 대해, 먹는 파이는 최대한 설탕이 많이 들은 파이, 안먹는 파이는 최대한 설탕이 적게 들은 파이인 것이 좋기에 B를 정렬해두고 생각하는 것이 좋습니다. 이 성질을 바탕으로 Dynamic 테이블을 아래와 같이 만듭니다.

D[i][j][k][0 or 1 or 2] : i개의 A, j개의 큰 B, k개의 작은 B

마지막으로 챙긴 과자가 A이면 0, B이면 1, 그냥 안먹으면 2

D[i][j][k][0]에 대해 (A를 먹을 예정)

- 직전에 B를 먹었고 사이에 A를 하나 끼워넣을거라면 D[i-2][j][k][1] + A[i]

- 직전에 B를 먹었고 사이에 B를 하나 끼워넣을거라면 D[i-1][j][k-1][1] + A[i]

- 직전에 A를 먹었고 사이에 A를 하나 끼워넣을거라면 D[i-2][j][k][0] + A[i]

- 직전에 A를 먹었고 사이에 B를 하나 끼워넣을거라면 D[i-1][j][k-1][0] + A[i]

- 직전에 안먹었으면 D[i-1][j][k][2] + A[i]

D[i][j][k][1]에 대해 (B를 먹을 예정)

- 직전에 B를 먹었고 사이에 A를 하나 끼워넣을거라면 D[i-1][j-1][k][1] + B[j]

- 직전에 B를 먹었고 사이에 B를 하나 끼워넣을거라면 D[i][j-1][k-1][1] + B[j]

- 직전에 A를 먹었고 사이에 A를 하나 끼워넣을거라면 D[i-1][j-1][k][0] + B[j]

- 직전에 A를 먹었고 사이에 B를 하나 끼워넣을거라면 D[i][j-1][k-1][0] + B[j]

- 직전에 안먹었으면 D[i][j-1][k][2] + B[j]

D[i][j][k][2]에 대해 (안 먹을 예정)

- 직전에 B를 먹었으면 D[i][j-1][k][1]

- 직전에 A를 먹었으면 D[i-1][j][k][0]

이렇게 D 테이블을 잡고 나면 채워나가면 됩니다. 그런데 D[3000][100][100][3]을 잡으니 메모리가 터져서 i의 관점에서 참조하는게 인접한 2, 3개밖에 없는 점을 이용해 D 테이블을 D[10][100][100][3]으로 축소시키고 5로 나눈 나머지로 계산을 하도록 했습니다.(마치 circular queue와 비슷하게)

https://github.com/blisstoner/BOJ/blob/master/10777.cpp