ABC_140_D - Face Produces Unhappiness

[zeikar]

Problem link

https://atcoder.jp/contests/abc140/tasks/abc140_d

Problem Summary

사람들이 L, R 방향을 바라보며 서 있고, 서로 같은 방향을 바라보면 happy이다.
이때 k 번의 횟수만큼 (l, r) 범위의 사람들의 방향을 뒤집을 수 있다.
최대로 happy 하게 만들 수 있는 사람의 수를 구하는 문제.

Solution

딱 보면 어려운데 포인트를 잘 알아채면 굉장히 쉬워지는 문제.

unhappy한 사람들을 뒤집게 되면 happy 하게 변하는 사람의 수는 2명이다.

위 사실을 알면 쉽게 풀린다.

먼저 간단한 증명은 LLL ... RRR ... LLL 이 있을 때 R 을 뒤집어서 L로 만든다고 해보자. 그렇게 되면 RRR...R 의 내부의 happy는 그대로 이고 LR ... RL 처럼 서로 경계에 있는 unhappy인 사람은 LL....LL로 뒤집어 지면서 총 2명의 happy 가 추가된다.
또한, 배열의 양쪽 끝부분을 뒤집으면 1명만 증가하지만 그리디 하게 2명 증가하는 부분만 뒤집는다고 생각하면 된다.

최대로 happy할 수 있는 사람의 수는 n-1 이므로 이를 넘지 않도록 출력해주면 된다.

Source Code

#include <iostream>
#include <string>
using namespace std;

int main() {
	int n, k;
	string s;

	cin >> n >> k >> s;

	int happy = 0;
	for (int i = 1; i < n; i++)
	{
		if (s[i] == s[i - 1])
		{
			happy++;
		}
	}

	cout << min(n - 1, happy + 2 * k) << endl;
}