Boj 33879 c++ 러시아어 문제

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

 

나는 많은 조건 분기 문제에 정말 약한 것 같다.

 

문제

 

0과 1로 이루어진 문자열이 있다. 1이 2개 이상 연속한 경우에만 1의 개수를 세어준다고 한다.

0을 x개만큼 1로 바꿀 수 있을 때 1의 개수의 최댓값을 val[x] 라고 하자.

 

길이 n인 문자열과 q가 주어지고, q개의 질문(x)이 있을 때, 각 질문마다 val[x]의 값을 출력하면 되는 문제이다

 

 

관찰

 

처음에는 이상한 관찰을 했었다.

"1과 0 사이의 간격이 짧을 수록 좋다"

하지만 당연하게도 수많은 반례들이 쏟아져 나왔다.

 

이 문제에서 했어야 하는 가장 핵심적인 관찰은 

0을 1로 바꿀 때 늘어나는 1의 개수가 3, 2, 1인 행동이 있다는 것이다.

 

01010의 가운데 값을 채우는 경우는 1의 개수가 3이 늘어난다.

고립된1이 양쪽에 있고, 가운데 1을 채움으로써 3개의 1을 확보하기 때문이다.

 

010 에서 오른쪽, 왼쪽 0을 1로 채우는 경우에는 2가 늘어난다. 고립된 1을 하나 없애기 때문이다.

 

그리고 나머지 경우에서의 행동은 모두 인접한 1을 추가하는 것으로 1이 늘어난다.

 

그리디하게 생각하면 1의 개수가 가장 많이 늘어나는 행동부터 먼저 하면 된다.

 

즉, 01010을 모두 채워주고

남은 것 중에서 010 채워주고,

또다시 남은 0을 채주면 된다.

 

하지만 3가지 조건에 걸리지 않는

00000000..00000이라는 치명적인 반례가 존재하니 조심해야 한다.

이 경우에는 val[x]의 값은  {0, 2, 3, 4 .....}로 그냥 출력해주고 끝내면 된다.

 

그리고 구현할 때 정말 고생하고 싶지 않으면 문자열에 1을 미리 채워넣으면 안된다.

똑같이 3을 증가시키는 행동이라도 하는 순서에 따라서 val[x]의 값이 늘어나기 때문에

순서까지 고려해줘야 하는 불상사가 발생하기 때문이다.

 

 

 

그리고 구현 테크닉 중에서 1가지 유의점.

 

문자열이 시작하는 부분에서의 1010

문자열이 끝나는 지점에서의 0101

모두 01010과 같은 취급을 받는다.

 

마찬가지로 시작 10, 끝 01, 010 모두 1이 1개 고립된 경우이다.

 

때문에, 귀찮은 예외처리를 피하기 위해서는 

s의 양 끝에 0을 몇개정도 더해주어야 한다.

 

 

 

고립된 '1' 이라는 점에 주목하여 구현하는 것이 문제의 핵심이었지만.... 모든 예외를 하드코딩해버렸다

 

정답코드

 

 

#include <bits/stdc++.h>
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long 
using namespace std;

int32_t main() {
	fastio
	int n, q;
	string s;
	cin >> n >> q >> s;
	vector<int> val(n+1, 0);
	
	if(n == 1) {
		val[0] = 0;
	}
	else if(n == 2) {
		if(s == "11") {
			val[0] = 2;
		}
	}
	else {
		for(int i = 0; i < n; i++) {
			if(i == 0) {
				if(s[i] == '1' && s[i+1] == '1')val[0] += 1;
				continue;
			}if(i == n-1) {
				if(s[i] == '1' && s[i-1] == '1')val[0]+= 1;
				continue;
			}
			if(s[i] == '1') {
				if(s[i-1] == '0' && s[i+1] == '0')continue;
				val[0] += 1;
			}
		}	
	}
	int cnt = 0;
	if(n >= 4) {
		if(s[n-1] == '1' && s[n-2] == '0' && s[n-3] == '1' && s[n-4] == '0') {
			cnt++;
			val[cnt] = val[cnt-1] + 3;
			s[n-2] = '1';
		}
		if(s[0] == '1' && s[1] == '0' && s[2] == '1' && s[3] == '0') {
			cnt++;
			val[cnt] = val[cnt-1] + 3;
			s[1] = '1';
		}
	}
	if(s == "101") {
		s[1] = '1';
		cnt++;
		val[cnt] = val[cnt-1] + 3;
	}
	for(int i = 0; i < n-4; i++) { //01010
		if(s[i] == '0' && s[i+1] == '1' && s[i+2] == '0' && s[i+3] == '1' && s[i+4] == '0') {
			cnt++;
			val[cnt] = val[cnt-1] + 3;
			s[i+2] = '1';
		}
	}
	if(n >= 2) {
		if(s[n-1] == '1' && s[n-2] == '0') {
			cnt++;
			val[cnt] = val[cnt-1] + 2;
			s[n-2] = '1';
		}
		if(s[0] == '1' && s[1] == '0') {
			cnt++;
			val[cnt] = val[cnt-1] + 2;
			s[1] = '1';
		}
	}
	for(int i = 0; i < n-2; i++) { //010
		if(s[i] == '0' && s[i+1] == '1' && s[i+2] == '0') {
			cnt++;
			val[cnt] = val[cnt-1] + 2;
			s[i] = '1';
		}
	}
	bool all_zero = true;
	for(int i = 0; i < n; i++) {
		if(s[i] == '1') {
			all_zero = false;
			break;
		}
	}
	if(all_zero) {
		val[1] = 0;
		if(n >= 2) {
			val[2] = 2;
			for(int i = 3; i <= n; i++) {
				val[i] = i;
			}
		}
	}
	else {
		for(int i = 0; i < n; i++) {
			if(s[i] == '0') {
				cnt++;
				val[cnt] = val[cnt-1] + 1;
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		val[i] = max(val[i], val[i-1]);
	}
	while(q--) {
		int x;
		cin >> x;
		cout << val[x] << "\n";
	}
}
// 1is break
// 0is work
/*  1. 01010 --> + 3 (1010, 0101)
	2. 010 --> + 2 (10,  01)
	3. remaining 0
	4. 1
*/