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

문제

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

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

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

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

입력

첫째 줄에 돌상의 개수 N이 주어진다.

둘째 줄에 돌상이 나열된 순서대로, 각 돌상이 바라보고 있는 방향이 주어진다. 입력의 편의상 왼쪽은 1, 오른쪽은 2라고 하자.

출력

최대한 많은 깨달음을 얻기 위해 금을 칠하였을 때, 얻을 수 있는 깨달음의 양을 출력한다.

제한

1 ≤ N ≤ 100,000

풀이

DP 문제!
연속된 부분 수열 중에서, 1또는 2로 이루어진 가장 긴 수열의 길이를 구하면 된다. 단, 다른 숫자를 포함할 경우, 개수를 차감한다.

예를 들어,
1 2 2 1 2 2 2 1
의 경우, 2 2 1 2 2 2에서 1이 1개, 2가 5개로 5 - 1 = 4가 연속된 부분 수열의 최대이다.

1912: 연속합 문제와 비슷하다.

left_max와 right_max 2개로 나누어 부분 수열의 최댓값을 계산해주었다.
각각 왼쪽 돌상과 오른쪽 돌상의 현재 개수의 최대치를 뜻한다

input이 맞는 방향의 불상일 경우, 해당 max는 ++, 다른 방향의 max는 --해준다.
input마다 각 방향의 max를 확인한 후, total_max보다 크면 total_max를 갱신한다.
그 후, 각 방향의 max를 확인하여, 음수일 경우 0으로 바꿔준다. max가 음수라는 것은 이미 max가 0인 상태에서 다른 방향의 input을 받았다는 뜻으로, 다음 input부터 부분 수열을 다시 계산할 수 있도록 0으로 바꿔준다.

예를 들어, 1 2 2를 보자.
1. input 1: left_max == 1, right_max == -1, total_max == 1 <-- right_max가 음수이므로, 0으로 바꿔준다.
2. input 2: left_max == 0, right_max == 1, total_max == 1
3. input 2: left_max == -1, right_max == 2, total_max == 2 <-- left_max가 음수이므로, 0으로 바꿔준다.

따라서 정답은 2.

코드

#include <iostream>

using namespace std;

int n, left_max, right_max, total_max, input;

void find_maximum(void);

int main(void)
{
	find_maximum();

	return (0);
}

void find_maximum(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	int i = -1;
	while (++i < n)
	{
		cin >> input;
		input == 1 ? left_max ++ : left_max --;
		input == 2 ? right_max ++ : right_max --;
		if (left_max > total_max || right_max > total_max)
			total_max = max(left_max, right_max);
		if (left_max < 0)
			left_max = 0;
		if (right_max < 0)
			right_max = 0;
	}

	cout << total_max;

	return ;
}

성공 ~!