원티드 쇼미더코드 2022년 3회차 - A번 신을 모시는 사당

원티드 쇼미더코드 3회차 문제가 백준에 올라와서 정리해봄

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

27210번: 신을 모시는 사당

돌상 N개가 왼쪽 혹은 오른쪽을 보고 있는데, 연속된 곳을 색칠했을 때 얻을 수 있는 깨달음의 최대값을 구하는 문제이다. 
| (왼쪽을 바라보는 금색 돌상의 개수) - (오른쪽을 바라보는 금색 돌상의 개수) | = 깨달음 값

N이 최대 10만이여서 N^2 미만의 복잡도로 풀어야했다. 부분 수열 합의 최대값을 구하는 문제가 되기 때문에 카데인 알고리즘의 O(N) 시간복잡도를 생각해서 부분합을 구하는 방식으로 풀었다. 

햇깔리는 점은 한 방향이 쭉 나오다가 하나 반대방향이 나오는 경우 부분합이 감소하는 것을 어떻게 구현할지 여부였는데, 그래서 왼쪽방향으로의 깨달음 값의 부분합, 오른쪽 방향으로의 깨달음 값의 부분합 2개 배열로 나눠서 계산했다. 

#include <bits/stdc++.h>
using namespace std;
#define FASTIO cin.tie(nullptr)->sync_with_stdio(false)

int N, A[100001], L[100001], R[100001];

int main() {
    FASTIO;
    cin >> N >> A[0];
    A[0] == 1 ? L[0] = 1 : R[0] = 1;
    for (int i = 1; i < N; ++i) {
        cin >> A[i];
        if (A[i] == 1) { // A[i]가 왼쪽 보는 경우
            L[i] = L[i - 1] + 1;
            R[i] = max(R[i - 1] - 1, 0);
        } else { // 오른쪽 보는 경우
            R[i] = R[i - 1] + 1;
            L[i] = max(L[i - 1] - 1, 0);
        }
    }

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        ans = max({ans, L[i], R[i]});
    }
    cout << ans;
    return 0;
}