Educational Codeforces Round 112 복기

다음 라운드까지 기간이 많이 남아서 가상 참가로 연습해야겠다 생각하던 중에 시계를 보니 11시여서 라운드가 보통 11시 35분에 시작하기도 하고 자기 전에 라운드 하나를 진행하면 좋겠다 싶어서 Educational Codeforces Round 112에 가상참가했다. 

이제 A, B는 빠르진 않지만 안정적으로 풀기 시작하게된것 같다. 하지만 한번 꼬이기 시작하면 멘탈이 흔들리는 게 문제라 문제를 꼼꼼하게 읽고 한 번에 맞추도록 연습해야겠다.

https://codeforces.com/contest/1555/problem/C

Problem - C - Codeforces

문제 C까지만 풀려고 했는데 C가 쉽게 풀리지 않기도하고 충동적으로 시작한 라운드라 너무 피곤한 상태라 푸는 걸 포기하고 자기 전까지 머릿속으로 풀이를 생각해봤었다.

행이 2개고 열이 m개인 게임판이 있을 때 각 칸에는 양의 정수개의 코인이 있다. 플레이어는 (1,1)에서 (2, m)까지 최단거리로 이동하면서 각 칸의 코인을 얻을 수 있다.

플레이어 1이 진행한 후에 플레이어 2가 진행하는데 플레이어 1이 이미 코인을 얻은 칸은 플레이어 2가 코인을 얻을 수 없다. 최종 스코어를 플레이어 2가 획득한 코인의 개수라고 할 때 플레이어 1은 최종 스코어를 최대한 작게 만들고자 하고 플레이어 2는 최종 스코어를 최대한 크게 만드려고 한다.

플레이어 1과 플레이어 2가 목적을 달성하기 위해 최선의 선택을 했다고 가정했을 때 최종 스코어를 출력하는 문제.

게임판이 n * m 이였다면 경우의 수가 무수히 많겠지만 2 * m이기 때문에 최단거리로 가능 경우는 1부터 m중 언제 한번 내려갈지만 생각하면 된다. 플레이어가 두 명이기 때문에 완전 탐색으로 푼다면 O(n^2)의 시간 복잡도를 가진다.

여기서 좀 더 생각을 해본다면 두번째 플레이어의 선택지는 m개가 아니라 2개밖에 없다는 것을 알 수 있다.

플레이어 1이 임의의 경로로 지나가면서 코인을 획득한 상황.

이 때, 플레이어 2는 코인을 최대한으로 얻기 위해서는 두 개의 행 중 하나를 선택해 쭉 지나가는 방법을 선택해야만 한다. 그러므로 임의의 플레이어 1의 경로마다 플레이어 2의 선택지는 두 가지밖에 없다.

 for(int t = 0; t < T; t++){
        scanf("%d", &n);
        int up[n];
        int down[n];
        for(int i = 0; i < n; i++) scanf("%d", &up[i]);
        for(int i = 0; i < n; i++) scanf("%d", &down[i]);

        if(n == 1) {
            printf("0\n");
            continue;
        }

        for(int i = n-2; i >= 0; i--) up[i] = up[i] + up[i+1];
        for(int i = 1; i < n; i++) down[i] = down[i] + down[i-1];
        
        int min = up[1] > down[n-2] ? down[n-2] : up[1];
        for(int i = 1; i < n-1; i++) {
            int max = up[i+1] > down[i-1] ? up[i+1] : down[i-1];
            if(min > max) min = max;
        }
        printf("%d\n", min);
    }

플레이어 1이 i번째 칸에서 아래 행으로 내려갈 때 위의 행에서  i+1부터 n까지 더한 값과 아래 행에서 1부터 i-1까지 더한 값을 비교해 큰 값을 다른 케이스와 비교하여 모든 케이스 중 가장 작은 값을 찾으면 된다.

이 계산을 빠르게 하기위해 위 행의 값은 오른쪽부터 왼쪽으로 누적한 값을 배열에 저장하고 아래 행의 값은 왼쪽부터 오른쪽으로 누적한 값을 배열에 저장한다.

복기를 하면서 글로 적다보니 머릿속으로 정리가 되면서 솔루션을 보지 않고 복기 글을 모두 작성했다.

머릿속으로 정리가 되고 나니 쉬웠던 문제. m * n 게임판으로 문제를 일반화하고 알고리즘을 생각하다 보니 문제를 어렵게 생각했던 거 같다. C, D 문제부터는 문제를 정확하게 이해하기 위해 시간을 쓰는 걸 아까워하지 않는 게 중요할 것 같다.