ABC364 E - Maximum Glutton

Competitive Programming C++ AtCoder

2024-07-28

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc364/tasks/abc364_e

원문 링크
https://atcoder.jp/contests/abc364/editorial/10550

스누케 군이 먹는 요리의 집합에서 스누케 군이 마지막으로 먹는 요리를 뺀 집합에 대해서, 거기에 포함되는 요리의 단맛의 합계 / 짠맛의 합계가 각각 \(X\)이하, \(Y\) 이하가 되는 점 (*) 에 주의해 봅시다.

단맛의 합계가 \(X\)를 넘지 않으면서, 짠맛의 합계가 \(Y\)를 넘지 않도록 요리의 집합 \(S\)를 고를 때, \(S\)에 포함되는 요리의 개수의 최댓값을 \(x\)라고 둡시다. 이 때, 원래 문제의 답은 \(\min(x + 1, N)\)으로 나타낼 수 있습니다.
(증명: \(x = N\)일 때는 자명하며, \(x < N\)일 때는 \(S\)에 포함되는 요리를 먼저 나열하는 것으로 최소 \(x + 1\)개는 먹을 수 있으며, 반대로 \(x + 2\)개째를 먹을 수 있다고 하면 (*) 로부터 원소 수 \(x + 1\)의 \(S\)를 취할 수 있다는 것이 되어 모순이 됩니다. 따라서 먹을 수 있는 요리의 개수의 최댓값은 \(x + 1\)입니다.)

그럼, 단맛의 합계가 \(X\)를 넘지 않으면서, 짠맛의 합계가 \(Y\)를 넘지 않도록 하는 조건을 토대로 고를 수 있는 요리의 개수의 최댓값을 계산하는 것을 생각해봅시다. 가장 간단한 접근은 다음과 같이 DP를 이용하는 것이지만, \(O(NXY)\)의 시간복잡도가 되어버려 시간 제한에 맞출 수 없습니다:

• \(dp_{i, j, k} =\)(요리 \(1, 2, …, i\) 중에서 단맛의 합계가 \(j\), 짠맛의 합계가 \(k\)가 되도록 요리를 선택했을 때 고를 수 있는 개수의 최댓값)

여기서, 이 문제에 대해서는 \(N\)의 값이 \(X, Y\)보다 훨씬 작은 점에 주목해서, DP의 키와 값을 바꾸는 전형적인 접근을 이용합니다. 구체적으로는, 짠맛의 합계를 값으로 가지면서,

• \(dp’_{i, j, k} =\)(요리 \(1, 2, …, i\) 중에서 단맛의 합계가 \(j\)가 되도록 \(k\)개의 요리를 선택했을 때, 짠맛의 합계의 최솟값)

으로 두면, \(O(N^2X)\)의 시간복잡도로 DP 테이블을 채울 수 있습니다. 그 다음엔, \(dp’_{i, j, k} \leq Y\)를 만족하는 \(j\)가 존재하도록 하는 \(k\)의 최댓값을 찾으면 됩니다.

웰노운인데 못풀었다

DP라는 감은 바로 왔지만, 차원을 바꾸는 생각을 제 떄 해내지 못하고 결국 대회 중에 풀지 못했다.
덕분에 이번엔 A - D 4솔 마무리로, 레이팅이 4점 떨어졌다…
방어에 성공했다면 성공한 것일까.

SSAFY 입과 이후 바빠져서 블로그 관리에 소홀한 벌을 받는 듯 하다.
더 열심히 해야지.