문제 유형: 구현

문제 URL: https://codeforces.com/contest/1055/problem/B

  앨리스(Alice)의 머리카락들이 계속 자라고 있습니다. 앨리스는 그래서 미용사에게 찾아갔습니다. 앨리스는 모든 머리카락이 최대 l 센티미터(Centimeter)가 될 수 있도록 머리를 자르고 싶습니다. 앨리스의 머리카락 개수는 N개이며, 각 머리카락을 1번부터 N번까지의 번호로 다룬다고 합시다.

  미용사가 가위를 이용해 한 번 머리카락을 자르면, 미용사는 길이가 l보다 큰 머리카락의 길이를 l이 되도록 만들 수 있습니다. 이 때 머리카락은 1번부터 N번까지 차례대로 위치하며 가위로 서로 인접한 머리카락들을 한 번에 자를 수 있습니다. 미용사는 가능한 빠르게 앨리스의 머리를 손질하고 싶습니다. 미용사가 가위질을 할 때마다 1초가 소요된다고 가정했을 때, 앨리스의 머리를 손질하는 최소 시간을 구하면 되는 문제입니다.

  또한 앨리스는 미용사에게 언제 갈 지를 정확히 결정하지 않았기 때문에, 특정한 시각에 자신의 머리카락의 길이를 미용사에게 알려주면서 머리 손질 시간을 물어보고자 합니다. 이 때 정확히 두 가지 유형의 쿼리(Query)가 있습니다.

  0) 앨리스가 지금 미용사에게 가면 머리를 손질하는데 얼마나 시간이 걸릴 지 물어보는 쿼리입니다.

  1) P와 D가 이어서 입력되며, P번째 머리카락이 D 센티미터만큼 자랐다는 의미를 가지는 쿼리입니다.

  기본적으로 앨리스가 원하는 머리카락 최대 길이인 l은 프로그램이 끝날 때까지 동일한 값을 가진다고 보면 됩니다.

  이 문제는 대표적인 구현 문제 유형이라고 볼 수 있습니다. 또한 인접한 머리카락들을 잘 살펴보는 것이 중요합니다. 그러므로 일단 맨 처음에 주어진 초기 상태를 보고 머리카락을 몇 번 잘라야 하는지를 검사합니다. 이후에 특정한 위치의 머리카락이 길어질 때마다 그 왼쪽과 오른쪽에 있는 머리카락과의 관계를 확인하여, 가위질 횟수가 증가할 지 혹은 감소할 지를 판단하면 됩니다.

  총 9가지 경우의 수만 고려하면 돼요. 머리카락이 l보다 작다가, l보다 길어진 특정한 머리카락의 위치를 (K), 왼쪽과 오른쪽에 있는 머리카락이 각각 길다면 (긴), 짧다면 (짧)이라고 합시다. 또한 머리카락 중에서 K가 가장 왼쪽 혹은 오른쪽에 위치할 때, 끝 부분은 (끝)이라고 합시다.

  1) 짧K짧: K 위치를 잘라야 하므로 가위질 횟수 1 증가

  2) 짧K긴: 오른쪽 가위질에 포함될 수 있으므로 가위질 횟수 그대로

  3) 긴K짧: 왼쪽 가위질에 포함될 수 있으므로 가위질 횟수 그대로

  4) 긴K긴: 왼쪽과 오른쪽 가위질에 모두 포함될 수 있으므로 가위질 횟수 1 감소

  5) 끝K짧: K 위치를 잘라야 하므로 가위질 횟수 1 증가

  6) 끝K긴: 오른쪽 가위질에 포함될 수 있으므로 가위질 횟수 그대로

  7) 짧K끝: K 위치를 잘라야 하므로 가위질 횟수 1 증가

  8) 긴K끝: 왼쪽 가위질에 포함될 수 있으므로 가위질 횟수 그대로

  9) 끝K끝: 원소가 1개인 경우이므로 가위질 횟수 1 증가

  위 9가지 경우의 수를 고려하여 전체 가위질 최소 횟수를 구하는 프로그램을 작성하면 됩니다.

※ 입출력 예시 ※

4 7 3
1 2 3 4
0
1 2 3
0
1 1 3
0
1 3 1
0

1
2
2
1

※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0) 

#include <iostream>
using namespace std;

long long a[100001];
long long n, m, l;

int main(void) {
	cin >> n >> m >> l;
	int res = 0;
	cin >> a[0];
	if(a[0] > l) {
		res++;
	}
	for(int i = 1; i < n; i++) {
		cin >> a[i];
		// 초기 상태에서 가위질 횟수를 구합니다. 
		if(a[i] > l) {
			if(a[i - 1] <= l) {
				res++;
			}
		}
	}
	for(int i = 0; i < m; i++) {
		int oper;
		cin >> oper;
		if(oper == 0) {
			cout << res << '\n';
		} else {
			int x, length;
			cin >> x >> length;
			int count = 0;
			// 머리카락이 l보다 짧았다가, l보다 길어져서 '자를 머리카락'이 되는 경우 
			if(a[x - 1] <= l && a[x - 1] + length > l) {
				bool find = false; // 원소가 1개인 경우를 체크하기 위한 목적 
				if(x - 2 >= 0) { // 왼쪽 머리카락 확인
					if(a[x - 2] <= l) count++; // (짧)
					else count--; // (긴)
					find = true;
				} 
				if(x < n) { // 오른쪽 머리카락 확인
					if(a[x] <= l) count++; // (짧)
					else count--; // (긴)
					find = true;
				}
				if(!find) res++;
			}
			if(count >= 1) res++;
			else if(count == -2) res--;
			a[x - 1] += length;
		}
	}
	return 0;
}