취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 27210번 문제인 신을 모시는 사당이다.
문제는 아래 링크를 확인하자.

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

각 석상의 인덱스를 1부터 N까지의 정수로 순서대로 부여하자. 구간 [0,k]에 속한 왼쪽을 향하는 석상의 수를 L[k], 오른쪽을 향하는 석상의 수를 R[k]라 하자. 이 때 구간 [x,y]에 속한 왼쪽을 향하는 석상의 수는 L[y]-L[x-1], 오른쪽을 향하는 석상의 수는 R[y]-R[x-1]로 나타낼 수 있음을 관찰할 수 있다.

위의 관찰로부터 구하는 값은 (R[y]-L[y]) - (R[x-1]-L[x-1])의 절댓값의 최댓값과 같다는 점을 알 수 있다. 따라서 R[k]-L[k]의 최댓값과 최솟값을 각각 구해 둘의 차를 구하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int cnt = 0;
int mx = 0, mn = 0;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (N--) {
		int x; cin >> x;
		if (x == 1) cnt++;
		else cnt--;
		mx = max(mx, cnt), mn = min(mn, cnt);
	}

	cout << mx - mn;
}