Educational Codeforces Round 112-C. Coin Rows

문제 설명

앨리스와 밥은 $2\times m$ 크기의 격자판에서 게임을 하고 있다. $i$번째 행과 $j$번째 열에 위치한 격자는 $a_{i,j}$개 코인이 위치해 있다.

처음에 앨리스와 밥은 격자 $(1,1)$ 에 위치해 있다. 이들은 격자 $(2,m)$ 을 향해서 다음 동작을 수행한다.
가능한 움직임은 다음과 같다.

• 오른쪽으로 이동 $(x,y)->(x,y+1)$
• 아래쪽으로 이동 $(x,y)->(x+1,y)$

첫번째로 앨리스가 $(2,m)$ 을 향해서 움직인다. 앨리스는 방문한 모든 격자의 코인을 다 쓸어담는다. 단 처음과 끝도 포함.

두번째로 밥이 $(2,m)$ 을 향해서 움직인다. 이때 밥은 앨리스가 방문하지 않은 모든 격자의 코인을 다 쓸어 담는다. 즉 앨리스가 이미 방문한 곳은 코인이 존재하지 않으므로 코인을 담을 수 없다.

이 게임의 점수는 밥이 담은 코인의 개수로 정해진다.

앨리스는 점수를 최소화하고 싶고, 밥은 점수를 최대화 하고 싶다. 두 참가자가 최적의 방식으로 게임을 했을 때 점수는 몇점일까?

Input
첫번째 줄에는 테스트 케이스를 의미하는 정수 $t(1\le t\le {10}^4)$ 이 주어진다.

각 테스트 케이스의 첫번째 줄에는 격자판의 열의 길이인 $m(1\le m\le {10}^5)$ 가 주어진다.

각 테스트 케이스의 다음에는 격자판의 상태를 나타내는 정수가 두줄에 걸쳐서 주어진다. $a_{i,1},a_{i,2},...,a_{i,m}(1\le a_{i,j}\le {10}^4)$

Output
각 테스트케이스마다 두 참가자가 최적의 방법으로 게임을 진행했을때 얻을 수 있는 점수를 출력한다.

Example
input
3
3
1 3 7
3 5 1
3
1 3 9
3 5 1
1
4
7

output
7
8
0

문제 접근

사용한 알고리즘: 구성적 알고리즘, 구현, 누적합
걸린 시간 : 00:06
개인적으로 B번보다 쉽다고 느낀 문제. 경우의 수를 찾기 쉬웠다. 문제만 이해하면 풀 수 있을 것 같다.

모든 참여자는 무조건 오른쪽과 아래로만 이동할 수 있기 때문에 반드시 $i$ 번째 열에서 아래로 내려가야한다. 즉

형태로 반드시 움직여야 한다는 뜻이다.

앨리스가 이동할 수 있는 경로는 결국 열의 개수인 $m$개가 된다. 첫번째 열부터 시작해서 마지막 열까지 앨리스가 이동하고 남은 코인은 결국 오른쪽 위 부분하고 왼쪽 아래 부분만 밥이 먹을 수 있는데 밥은 점수를 최대화 하고 싶기 때문에 이 두 부분중에서 큰 값을 얻으려고 할 것이다.

즉 앨리스가 이동하는 각 경우에서 밥이 먹을 수 있는 코인의 최댓값을 구하고 그 값중에서 최소값을 구하면 두 사람이 최적의 플레이을 했을 때 얻을 수 있는 점수를 의미한다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int arr[2][n];
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < n; j++) cin >> arr[i][j];
        }

        int sum1 = 0, sum2 = 0, ans = 1e9;
        for(auto x : arr[0]) sum1 += x;
        for(int i = 0; i < n; i++){
            sum1 -= arr[0][i];
            ans = min(ans, max(sum1, sum2));
            sum2 += arr[1][i];
        }
        cout << ans << "\n";
    }
    return 0;
}