백준 31027 (C++) 물고기 게임

최초 업로드: 2025-10-29 20:22:16

최근 수정 시간: 2025-10-29 20:26:57

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] 물고기 게임

[문제 링크](https://www.acmicpc.net/problem/31027)

## 문제 설명

오토는 반쵸스시에서 곰치 커리를 대접받은 뒤, 그 보답으로 데이브에게 $2\times N$ 크기의 양식장을 만들어 주었다!

... 그렇게 해서 데이브와 오토가 게임을 하게 되었다. 오토는 $(1,1)$에 서 있고, 데이브는 $(2,N)$에 서 있다. $(1,1)$과 $(2,N)$을 제외한 칸에는 물고기가 있다. 데이브와 오토는 다음과 같은 턴을 $10^{100}$회 반복한다.

데이브와 오토는 물고기를 최대한 많이 가져가려고 한다. 이때, 오토가 가져가는 물고기의 마릿수와 데이브가 가져가는 물고기의 마릿수를 구해야 한다.

## 입력

첫 번째 줄에 양식장의 크기 $N$이 주어진다.

두 번째 줄에는 $A_{1,1}, A_{1, 2}, \cdots A_{1, N}$가 공백으로 구분되어 주어진다.

세 번째 줄에는 $A_{2,1}, A_{2, 2}, \cdots A_{2, N}$가 공백으로 구분되어 주어진다.

## 출력

최선을 다해 게임을 했을 때, 오토와 데이브가 가져가는 물고기의 마릿수를 공백으로 구분하여 출력한다.

## 풀이
- N이 짝수일 때
  - B가 처음에 위로 움직이면 A는 왼쪽 N/2+1부분, B는 오른쪽 N/2-1부분을 먹는다.
  - B가 처음에 왼쪽으로 움직이면 A가 위쪽, B가 아래쪽을 먹는 경우와 A가 왼쪽 절반, B가 오른쪽 절반 먹는 경우 두 가지 중 A가 더 적은 개수를 먹는 경우가 선택된다.
  - 위 두 가지 경우 중 작은 값이 선택된다.
- N이 홀수일 때
  - B가 처음에 위로 움직이면 A는 왼쪽 N/2+1부분, B는 오른쪽 N/2-1부분을 먹는다.
  - B가 처음에 왼쪽으로 움직이면
    - A가 N/2칸까지 가는 경우 A가 왼쪽 N/2부분, B가 오른쪽 N/2+1부분을 먹는다.
    - A가 N/2+1칸까지 가는 경우 A가 위쪽, B가 아래쪽을 먹는 경우와 A가 왼쪽 절반, B가 오른쪽 절반 먹는 경우 두 가지 중 A가 더 적은 개수를 먹는 경우가 선택된다.
    - 위 두 가지 경우중 큰 값이 선택된다.
- 결국 식을 정리하면 A가 먹는 개수는 max(min(왼쪽 N/2+1부분을 먹는 경우, 위쪽을 전부 먹는 경우), 왼쪽 N/2부분을 먹는 경우)로 세 값중 중간값이 선택된다.

``` c++
#include<bits/stdc++.h>
using namespace std;

long long preSum[2][500'001];

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 for(int i=0;i<2;i++) {
 for(int j=1;j<=n;j++) {
 cin >> preSum[i][j];
 preSum[i][j] += preSum[i][j-1];
 }
 }

long long A = max(min(preSum[0][n], preSum[0][n/2+1]+preSum[1][n/2+1]), preSum[0][n/2]+preSum[1][n/2]);
 cout << A << ' ' << preSum[0][n]+preSum[1][n]-A;
}
```