백준13955 Key Knocking

작성일 | In

문제 링크

  • http://icpc.me/13955

문제 출처

  • CERC 2016 K번

시간복잡도

  • O(N)

풀이

비트열의 길이가 3N이고, N번 조작해서 서로 다른 인접한 비트쌍을 2N-1개 만들어야 하고, 답은 항상 존재한다고 합니다.
문제의 조건을 보면 비트 3개마다 1번 조작해서 인접한 비트쌍을 2개씩 만들어야 하고, 맨 앞이나 맨 뒤에서 인접한 비트쌍이 1개 나온다는 것을 유추할 수 있습니다.

비트 3개로 만들 수 있는 경우의 수는 8입니다. 8개를 각각 봅시다.

1
2
3
4
5
6
7
8
000 : 1, 2번째 뒤집으면 110 -> 인접한 서로 다른 비트쌍 1개
001 : 2, 3번째 뒤집으면 010 -> 인접한 서로 다른 비트쌍 2개
010 : 010 -> 인접한 서로 다른 비트쌍 2개
011 : 1, 2번째 뒤집으면 101 -> 인접한 서로 다른 비트쌍 2개
100 : 1, 2번째 뒤집으면 010 -> 인접한 서로 다른 비트쌍 2개
101 : 101 -> 인접한 서로 다른 비트쌍 2개
110 : 2, 3번째 뒤집으면 101 -> 인접한 서로 다른 비트쌍 2개
111 : 1, 2번째 뒤집으면 001 -> 인접한 서로 다른 비트쌍 1개

최대 한 번의 조작으로 1개 혹은 2개의 서로 다른 인접한 비트쌍을 만들 수 있습니다.
위 방법으로 처음 3개의 비트를 조작할 수 있습니다.

4번째 비트부터는 3개씩 뒤에 붙이면서 한 번의 조작으로 새로운 서로 다른 비트쌍을 2개씩 만들어주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;

int f(string &s){
	int ret = 1;
	for (int i = 1; i < s.size(); i++){
		ret += s[i] != s[i - 1];
	}
	return ret;
}

int op[] = { 1, 2, 0, 1, 1, 0, 2, 1 };
vector<int> v;
string s;

void inv(int x){
	s[x] = s[x] == 0 ? 1 : 0;
}

int get(int x){
	int ret = 0;
	ret += s[x - 1] != s[x];
	ret += s[x] != s[x + 1];
	ret += s[x + 1] != s[x + 2];
	return ret;
}

void go(int x){
	if (x == 0){
		int now = s[0] * 4 + s[1] * 2 + s[2];
		if (op[now]) v.push_back(op[now]);
		return;
	}

	if (get(x) >= 2) return;

	inv(x), inv(x + 1);
	if (get(x) >= 2){
		v.push_back(x + 1); return;
	}
	inv(x), inv(x + 1);

	inv(x + 1), inv(x + 2);
	if (get(x) >= 2){
		v.push_back(x + 2); return;
	}
	inv(x + 1), inv(x + 2);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> s;
	int n = s.size() / 3;

	if (f(s) >= 2 * n){
		cout << 0; return 0;
	}
	for (auto &i : s) i -= '0';
	for (int i = 0; i < s.size(); i+=3) go(i);

	cout << v.size() << "\n";
	for (auto i : v) cout << i << " ";
}