백준 2138 c++ "전구와 스위치" -PlusUltraCode-

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

 

[필자 사고]

이 문제를 dp 혹은 greedy둘 중 많은 고민을 했따.

반복적인 과정이 없으므로 greedy라 판별했지만 어떻게 해당 문제를 접근해야 될지 아이디어가 떠오르지 않았다.

그래서 일단 무작정 for문으로 하나하나 해보기로 했다.

그런데 왠걸 됐다.

greedy는 매번 최적의 해를 찾아 떠나는 것이다. 해당 풀이법이 맞았다.

그러나 첫번째 경우의 수에 따라 해당 경우의 수가 달라지므로 그 부분만 주의해주면 된다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

함수별 설명:

1. Input()

• 사용자로부터 입력을 받습니다.
  • N: 전구의 개수
  • str1: 초기 전구 상태
  • str2: 목표 전구 상태

2. lightOn(int idx)

• idx번째 스위치를 누를 때 영향을 받는 전구를 반전시킵니다.
  • idx - 1, idx, idx + 1 위치의 전구가 모두 반전됩니다.
  • 단, idx가 마지막 전구일 경우 idx + 1은 없으므로 idx - 1, idx만 반전합니다.

3. Find_Count(int first)

• first가 1이면 처음 전구를 눌러서 시작하고, 0이면 누르지 않고 시작합니다.
• temp라는 임시 문자열을 str1로 초기화하고, 시뮬레이션을 수행합니다.
• 첫 번째 전구부터 차례로 목표 상태(str2)와 비교하면서 이전 전구가 다를 경우 현재 전구의 스위치를 눌러 반전시킵니다.
• 마지막까지 temp가 str2와 같아졌다면, 현재까지의 스위치 누른 횟수(count)를 최소값(resultCount)과 비교해 갱신합니다.

4. Game_Start()

• 두 가지 경우 모두 테스트:
  • 첫 번째 전구를 누르지 않는 경우: Find_Count(0)
  • 첫 번째 전구를 누르는 경우: Find_Count(1)
• 두 경우 중에서 최소 횟수를 출력합니다.
  • 둘 다 불가능할 경우(resultCount == INT_MAX)에는 -1 출력

---

핵심 로직 요약:

• 문제는 "앞에서부터 순차적으로 이전 전구의 상태를 맞춰간다"는 전략으로 해결됩니다.
• 단 한 가지 전략으로는 해결되지 않을 수 있기 때문에, "첫 번째 스위치를 누를지 여부"를 기준으로 두 가지 경우를 모두 시도합니다.
• 결과적으로 최소한의 스위치 조작으로 목표 상태에 도달할 수 있는 경우의 수를 구하며, 불가능할 경우 -1을 출력합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;

int N;
string str1, str2, temp;
int resultCount = INT_MAX;

void Input() {
	cin >> N;
	cin >> str1 >> str2;

}

void lightOn(int idx) {

	if (idx == N - 1) {
		temp[idx - 1] = (temp[idx - 1] == '0') ? '1' : '0';
		temp[idx] = (temp[idx] == '0') ? '1' : '0';
		return;
	}

	temp[idx - 1] = (temp[idx - 1] == '0') ? '1' : '0';
	temp[idx] = (temp[idx] == '0') ? '1' : '0';
	temp[idx+1] = (temp[idx+1] == '0') ? '1' : '0';
}

void Find_Count(int first) {
	temp = str1;
	int count = 0;

	if (first == 1) {
		temp[0] = (temp[0] == '0') ? '1' : '0';
		temp[1] = (temp[1] == '0') ? '1' : '0';
		count++;
	}

	for (int i = 1; i < N; i++) {
		if (str2[i - 1] != temp[i - 1]) {
			lightOn(i);
			count++;
		}
	}
	if(temp==str2) resultCount = min(resultCount, count);
}

void Game_Start() {
	
	Find_Count(0);
	Find_Count(1);

	if (resultCount == INT_MAX)cout << -1;
	else cout << resultCount;
}

int main(void) {
	Input();
	Game_Start();

}