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

27210번: 신을 모시는 사당

문제 요약

문제

신을 모시는 사당에는 신을 조각한 돌상 N개가 일렬로 놓여 있다. 각 돌상은 왼쪽 또는 오른쪽을 바라보고 서있다. 창영이는 연속한 몇 개의 돌상에 금칠을 하여 궁극의 깨달음을 얻고자 한다.

궁극의 깨달음을 얻기 위해서는 가능한 한 많은 금색 돌상들이 같은 방향을 바라보아야 한다. 방향이 다른 돌상은 깨달음에 치명적이다. 깨달음의 양은 아래와 같이 정의된다.

(왼쪽을 바라보는 금색 돌상의 개수) - (오른쪽을 바라보는 금색 돌상의 개수)

창영이는 궁극의 깨달음을 얻을 수 있을까?

사용 알고리즘

누적합

입출력

• 입력: 첫째 줄에 돌상의 개수 N이 주어진다. 둘째 줄에 돌상이 나열된 순서대로, 각 돌상이 바라보고 있는 방향이 주어진다. 입력의 편의상 왼쪽은 1, 오른쪽은 2라고 하자.
• 출력: 최대한 많은 깨달음을 얻기 위해 금을 칠하였을 때, 얻을 수 있는 깨달음의 양을 출력한다. ``` 예제1

입력 5 1 1 2 1 2 출력 2

## 풀이
굳이 dp로 풀 이유가 없다. 1을 -1로 보고 2를 1로 봐서 누적합을 구한다. 그리고 누적합의 최소치와 최대치를 기록한다. 최소치가 되는 부분부터 최대치가 되는 부분까지 칠하면 최소치와 최대치의 차 만큼 정답이 나온다.

## 어려웠던 점


## 배운 점 / 느낀 점


## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, s, smin, smax;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for(int i = 0; i < n; i++){
        int t;
        cin >> t;
        if(t==2){
            s++;
        }
        else{
            s--;
        }
        smin = min(s, smin);
        smax = max(s, smax);
    }
    cout << smax - smin; 


    return 0;
}