[백준][C++] 27210: 신을 모시는 사당

문제

풀이

다이나믹 프로그래밍, 누적 합 문제이다.

 

완전 탐색으로 해결하려고 하면 O(N * N)으로 시간 초과이다.

 

배열을 두 개를 사용하여 문제를 해결해야 한다. 

• 첫 요소가 왼쪽인 배열. 왼쪽이 과반수인 배열. (left)
• 첫 요소가 오른쪽인 배열. 오른쪽이 과반수인 배열. (right)
• 전체 배열을 탐색하면서 돌상이 왼쪽인 경우에는, left 배열의 깨달음의 양이 1 증가하면서, right 배열의 깨달음의 양이 1 감소한다. 
• 돌상이 오른쪽인 경우에는, left 배열의 깨달음의 양이 1 감소하면서, right 배열의 깨달음의 양이 1 증가한다. 
• 현재 배열의 깨달음의 양이 0미만이라면 해당 배열을 버린다.
• 현재 배열 2개의 깨달음의 양의 최대값이 답이다.

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int nums[100000];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        cin >> nums[i];
    }

    int answer = 0;
    
    // 금칠할 돌상의 배열의 첫 돌상이 왼쪽인 경우와 오른쪽인 경우를 나눠서 생각한다. 
    // 왼쪽을 중점으로 생각한 배열에서의 깨달음 양인 left
    int left = 0;
    // 오른쪽을 중점으로 생각한 배열에서의 깨달음 양인 right
    int right = 0;

    for (int i = 0; i < N; ++i)
    {
        // 현재 돌상은 배열안에 들어와 있다고 가정한다. 
        // 현재 돌상이 왼쪽인 경우에는 left는 1 증가하고, right는 1 감소한다.
        if (nums[i] == 1)
        {
            left++;
            right--;
        }
        // 현재 돌상이 오른쪽인 경우에는 left는 1 감소하고, right는 1 증가한다.
        else
        {
            left--;
            right++;
        }
        // 현재 배열의 깨달음 값이 0미만이라면 현재 배열을 버린다.
        left = left < 0 ? 0 : left;
        right = right < 0 ? 0 : right;

        // 현재 배열 2개의 깨달음 양의 최대값이 답이다.
        int maxi = max(left, right);
        answer = max(answer, maxi);
    }

    cout << answer;

    return 0;
}