백준 2040 - 수 게임

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

 

이 문제는 대단히 교육적인 문제이므로 꼭 공부하는 것을 추천한다.

게임 전략

A와 B 둘 다 최적으로 플레이를 한다고 했다. 이를 수식으로 표현하면 어떻게 될까?

 

A의 합을 $sum_{A}$, B의 합을 $sum_{B}$라고 하면 A와 B의 목표는 다음과 같이 정리할 수 있다.

 

A는 $sum_{A} - sum_{B}$를 최소화시켜야 한다.

 

B는 $sum_{A} - sum_{B}$를 최대화시켜야 한다. (혹은 $sum_{B} - sum_{A}$를 최소화시켜야 한다.)

 

그러면 저 값을 최적화 하는 문제로 표현할 수 있고 이는 동적 계획법으로 시도해볼 수 있을 것이다.

 

그런데 어떻게 동적 계획법을 해야 할까? 테이블을 다음과 같이 정의한다.

 

dp(i) := i번째 수까지 먹은 상태일 때 나 또는 상대 플레이어가 가져갈 수 있는 최적해

 

약간 생소해보일 수 있는 점화식이 등장했다. 하나의 테이블에서 A와 B 모두의 상태를 정의하기 때문이다. 이는 다음과 같이 해설할 수 있다.

 

dp(i)일 때는 어떤 연속합 $pref[L, i]$를 상대방이 먹었다는 뜻이다. 따라서 나는 i + 1번째부터 여러 원소를 먹을 수 있다. 그러면 내가 지금부터 i + 1부터 시작하는 어떤 연속 합 $pref[i + 1, R]$을 취한다면 상대방은 dp(R)부터 시작한다는 것은 당연하다.

 

이거를 위에 수식으로 정리한 목표에 대입해보자. $sum_{A} - sum_{B}$에서 내가 가져가는 값 $pref[i + 1, R]$이 $sum_{A}$이고 상대방이 가져갈 값 $sum_{B}$가 바로 dp(R)이 된다.

 

즉, 우리는 각 인덱스마다 $min(pref[i + 1, R] - dp(R))$을 구하면 된다. 그리고 A가 먼저 시작을 한다고 했으므로 dp(0)부터 점화식을 계산하면 자연스레 $min(sum_{A} - sum_{B})$을 구하게 된다.

 

점화식을 도출했으니 이를 탑 다운 dp로 해결하도록 하자. 시간 절약을 위해 누적합을 관리하면 좋다. 해당 점화식을 어떻게 계산할지 잘 모르겠으면 코드를 참조하도록 하자.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = int_fast64_t;
using pii = pair<int, int>;
 
int n;
int ar[3001];
int pref[3001];
int dp[3001];
 
int get_segsum(int l, int r)
{
  return pref[r] - pref[l - 1];
}
 
int memo(int cur)
{
  if (cur > n) return 0;
  auto &ret = dp[cur];
  if (ret != -1e9) return ret;
  ret = 0;
  int tmp = 1e9;
 
  for (int i = cur; i <= n; i++)
  {
    tmp = min(tmp, get_segsum(cur, i) - memo(i + 1));
  }
  return ret = tmp;
}
 
void solve()
{
  cin >> n;
  int tc = 3;
  while (tc--)
  {
    for (int i = n; i >= 1; i--)
    {
      cin >> ar[i];
    }
    for (int i = 1; i <= n; i++)
    {
      pref[i] = pref[i - 1] + ar[i];
    }
 
    fill(dp, dp + 3001, -1e9);
    int res = memo(1);
    if (res < 0) cout << "A\n";
    else if (res > 0) cout << "B\n";
    else cout << "D\n";
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록

보너스

앳코더 Educational DP에서는 위와 같은 전개로 풀 수 있는 문제가 하나 더 있다. 연습 삼아 풀어보자.

 

https://atcoder.jp/contests/dp/tasks/dp_l

L - Deque