[백준 16567] 바이너리 왕국 (C++)

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

문제

---

바이너리 왕국의 불쌍한 하인들은 매일 바이너리 길을 청소한다. 바이너리 길은 N개의 0 또는 1로 이루어진 수열이다.

0은 깨끗한 칸, 1은 더러운 칸을 의미한다.

그들은 "flip"이라는 기술만을 사용해서 청소를 한다. 이것은 연속된 더러운 칸을 깨끗하게 만드는 기술이다. 즉, 연속된 1을 모두 0으로 만든다.

바이너리 왕국의 악덕한 왕은 매일 하인들에게 M개의 시련을 내리는 것이 취미이다. 시련에는 2가지 종류가 있는데 다음과 같다.

• "0": 현재 길의 모든 칸을 깨끗하게 만들기 위한 "flip"의 최소 횟수를 하인들에게 크게 외치게 한다.
• "1 i": 바이너리 길의 i번째 칸을 더럽힌다. 단, 이미 더럽혀져 있다면 아무 일도 일어나지 않는다.

바이너리 왕국의 불쌍한 하인들의 슬픈 외침들을 출력하라.

 

입력

---

첫째 줄에 바이너리 길의 칸의 개수 N, 시련의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)

둘째 줄에 N개의 현재 바이너리 길의 상태가 주어진다.

그다음 M개의 줄에 걸쳐서 시련이 주어진다. 이때 0번 시련은 "0", 1번 시련은 "1 i"와 같이 주어진다. (1 ≤ i ≤ N)

 

출력

---

0번 시련이 주어졌을 때, 하인들의 외침을 개행으로 구분하여 출력하라.

 

문제 풀이

---

i번째 칸을 더럽히면 그 양 옆의 칸의 상태에 따라 구간의 수가 변한다.

 

아래 그림에서 하얀 칸은 깨끗한 칸, 검은 칸은 이번에 더러워진 칸, 회색 칸은 이전에 더러워진 칸들이다.

 

위와 같이 양 옆이 깨끗하다면, i번째 칸을 더럽히면 i번째 칸만을 청소해야 한다. 따라서 이 때 청소해야 하는 구간은 1개 증가한다.

 

위와 같이 양 옆 중 한쪽이라도 이미 더러워진 칸이 있다면 그 칸을 포함하는 구간에 연속적으로 이을 수 있다. 따라서 이 경우에는 청소해야 하는 구간이 늘어나지 않는다.

 

 

위와 같이 양 옆 칸 모두 이미 더러워진 칸이라면, 이전에는 현재 더러워진 칸 왼쪽을 포함하는 구간과 현재 더러워진 칸 오른쪽을 포함하는 구간 2개가 존재했지만 이제는 두 구간을 현재 더러워진 칸으로 이을 수 있다. 따라서 긴 하나의 구간이 생긴다. 증감의 변화로 보자면 청소해야 하는 구간의 개수가 한 개 줄어든 셈이 된다.

 

초기 상태도 비슷하다. 첫번째 칸인데 더럽거나 이전 칸이 깨끗한 칸인데 i번째 칸이 더럽다면 구간이 추가되고, 아니라면 이전에 만들어진 구간이 이어진다. 

 

위의 경우의 수를 코드로 구현해주면 된다.

#include <iostream>
using namespace std;

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

	int N, M, query, num;
	int answer = 0;
	cin >> N >> M;
	bool* isDirty = new bool[N+1];
	for (int i = 1; i < N+1; i++)
	{
		cin >> num;
		if (num == 0)
		{
			isDirty[i] = false;
		}
		else
		{
			isDirty[i] = true;
			if (i == 1 || isDirty[i - 1] == false)
			{
				answer++;
			}
		}
	}
	for (int i = 0; i < M; i++)
	{
		cin >> query;
		if (query == 0)
		{
			cout << answer << "\n";
		}
		else
		{
			cin >> num;
			if (isDirty[num] == true)
			{
				continue;
			}
			isDirty[num] = true;
			if (num == 1 && isDirty[2] == false)
			{
				answer++;
			}
			else if (num == N&& isDirty[N - 1] == false)
			{
				answer++;
			}
			else
			{
				if (isDirty[num - 1] == true && isDirty[num + 1] == true)
				{
					answer--;
				}
				else if (isDirty[num - 1] == false && isDirty[num + 1] == false)
				{
					answer++;
				}
			}
		}
	}
	return 0;
}