[그리디 알고리즘] 전구와 스위치

예제 입력 1

3

000

010

예제 출력 1

3

 

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

2138번: 전구와 스위치

- 이 문제를 풀기 위해서, 100000개의 스위치를 모두 누른다/누르지 않는다로 Brute Force를 돌려서는 풀 수 없다. (시간 복잡도 때문. 2^100000)

 

- 따라서, 아래와 같이 푼다. 각각의 스위치가 영향을 주는 전구를 표현하면 아래와 같다.

 

 

- 그런데 여기서, 이미 0번 스위치를 누른다/누르지 않는다가 이미 정해져 있다면 각각의 스위치가 영향을 주는 전구는 아래와 같이 달라진다.

 

- 이 때, 0번 전구에 영향을 주는 스위치는 #1번 스위치 뿐이다. 따라서, 만들고자 하는 상태가 주어졌을 때, 0번 전구의 상태가 서로 다르면, 반드시 #1번 스위치를 누를 수 밖에 없는 것이다.

 

- #1번 스위치가 눌릴지 말지 정해지면, 1번 전구 상태에 영향을 주는 것은 #2번 스위치 밖에 없게된다. 1번 전구가 만들고자 하는 상태와 같을 경우 #2번 스위치를 누르지 않아야하고 다르면 #2번 스위치를 눌러야만 한다.

 

- 이런식으로 반복하여 진행했을 때, 최종적으로 현재 전구의 상태와 만들고자 하는 상태가 같으면 가능한 것이고, 다르다면 불가능하다는 것을 의미한다.

 

- 따라서, (1) 0번 스위치를 누르지 않았을 때 위 알고리즘을 돌리고 (2) 0번 스위치를 눌렀을 때 위 알고리즘을 총 2번 돌려봐서 가능 할 경우 최소값이 정답이 된다.

#include <stdio.h>
#define MIN(a,b) ((a)<(b)?(a):(b))

constexpr int MAX_SIZE = 100000;

int first[MAX_SIZE];
int copyFirst[MAX_SIZE];

int second[MAX_SIZE];

int N;

void push(int blubArray[], int switchNum)
{
	for (int i = switchNum - 1; i <= switchNum + 1; i++)
	{
		if (i >= 0 && i < N)
		{
			blubArray[i] = 1 - blubArray[i];
		}
	}
}

bool go(int blubArray[], int targetBlubArray[], int& result)
{
	int ans = 0;

	for (register int i = 1; i < N; i++)
	{
		if (blubArray[i-1] != targetBlubArray[i-1])
		{
			push(blubArray, i);
			ans++;
		}
	}
	result = ans;

	for (register int i = 0; i < N; i++)
	{
		if (blubArray[i] != targetBlubArray[i])
		{
			return false;
		}
	}

	return true;
}

int main(void)
{
	int ans = -1;
	int nowAns = 0;

	scanf("%d", &N);

	for (register int i = 0; i < N; i++)
	{
		scanf("%1d", &first[i]);
		copyFirst[i] = first[i];
	}

	for (register int i = 0; i < N; i++) 
		scanf("%1d", &second[i]);

	// 0번 스위치를 안눌렀을 때
	if (go(first, second, nowAns))
	{
		if (ans == -1) ans = nowAns;
		else ans = MIN(ans, nowAns);
	}

	// 0번 스위치를 눌렀을 때
	push(copyFirst, 0);
	nowAns = 1;

	if(go(copyFirst, second, nowAns))
	{
		nowAns++; // 처음 누르고 시작했으므로
		if (ans == -1) ans = nowAns;
		else ans = MIN(ans, nowAns);
	}

	printf("%d\n", ans);

	return 0;
}