[백준 13955번] Key Knocking

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

최대 n번의 operation을 이용해서 비트의 가중치가 2n이상이 되도록 하게 하는 문제다.

주어지는 비트의 길이가 3n이므로 가중치가 2n이 되기 위해서는

최소 3번의 비트마다 한번 flip마다 가중치가 2씩 더해져야 한다.

 

flip한번으로 3개의 비트의 가중치가 가장 커지는 경우를 보면(이웃 비트로 인한 가중치)

000 → 최대 가중치 1

001 → 최대 가중치 2

010 → 가중치가 이미 2로 최대임

011 → 최대 가중치 2

100 → 최대 가중치 2

101 → 가중치가 이미 2로 최대임

110 → 최대 가중치 2 

111 → 최대 가중치 1

 

000과 111을 제외하고 모두 이웃 가중치를 2로 만들 수 있다. (본인 포함하면 3)

따라서 비트를 3개씩 붙이면서 최대로 가중치를 만드는 경우로 뒤집으면 된다.

비트는 3개씩 붙이되 이웃비트 검사는 맨 마지막 세 비트를 제외하고 4개씩 검사해서 가중치를 검사해야 한다.

맨 마지막 세 비트를 제외해도 되고 처음 세 비트만 먼저 가중치를 검사해도 된다.

(마지막 비트 뒤에 오는 비트로 인해 가중치가 더해지기 때문)

 

#include <iostream>
#include <vector>
#include <string>
#include <bitset>
#define endl "\n"
using namespace std;

string s;
int n, w, tmp, start[8] = {1,2,0,1,1,0,2,1};

// 가중치 계산기
int cal(string s){
	int tmpw = 0;
	for(int i = 0; i < s.length()-1; i++){
		if(s[i] != s[i+1]) tmpw++;
	}
	return tmpw;
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> s;
	vector<int> ans;
	w = cal(s);
	n = s.length()/3;
	if(w >= 2*n){
		cout << 0;
		return 0;
	}
	for(auto &v : s) v -= '0';
	for(int i = 0; i < s.length(); i+=3){
		if(i == 0){	// 처음 세 비트만 먼저 계산
			tmp += (s[0]*4+s[1]*2+s[2]*1);
			if(start[tmp]) ans.push_back(start[tmp]);
			continue;
		}
        // 이후부턴 4개씩 검사
        // 안뒤집었을 때의 가중치
		tmp = cal(s.substr(i-1,4));
		if(tmp >= 2) continue;
        // 1,2번을 뒤집는 경우의 가중치
		s[i] = 1-s[i]; s[i+1] = 1-s[i+1];
		tmp = cal(s.substr(i-1,4));
		if(tmp >= 2){
			ans.push_back(i+1);
			continue;
		}
		s[i] = 1-s[i];s[i+1] = 1-s[i+1];
        // 2,3번을 뒤집는 경우의 가중치
		s[i+1] = 1-s[i+1]; s[i+2] = 1-s[i+2];
		tmp = cal(s.substr(i-1,4));
		if(tmp >= 2){
			ans.push_back(i+2);
			continue;
		}
		// 위의 세개의 케이스에서 하나라도 가중치가 2를 넘으면 continue
        // 비트3개당 가중치가 2이상이면 되기 때문에
	}
	cout << ans.size() << endl;
	for(auto k : ans) cout << k << " ";
}