<백준알고리즘>그리디 알고리즘 2138번

백준 2138번

접근 과정

1. 주어진 숫자와 정답 숫자를 비교하여 가장 먼저 차이가 나는 곳 부터 마지막으로 차이가 나는 곳을 범위로 해서 스위치를 작동하면 최소로 해서 구할 수 있지 않을 까 생각을 해봤는데 만약에 답이 나오지 않을 경우엔 별다른 기준이 없다면 시간 초과에 걸릴 것이므로 다른 접근 법을 생각해 보기로 했다.

2. 위와 마찬가지로 DFS로 접근하면 입력값의 범위가 너무 커 무조건 시간초과가 날 것이라고 생각했다.

2-1. DFS를 살짝 보완하여 set에 다가 이미 나온 범위에 대한 중복을 설정하여 값을 갱신하면 괜찮지 않을까 했는데 그럼 같은 위치에서 같은 형태가 나오는 것이 아닌 이상 2번과 별 다를게 없다고 생각하여서 다른 접근법을 생각하기로 했다.

3. 마지막으로 알고리즘 분류를 봤는데 그리디 알고리즘이라고 되어있었다. 처음엔 이걸 보고 처음부터 진행하면서 동시에 같은지 비교를 해주어 만약 같다면 굳이 바꾸지않고 같지 않다면 바꾸지 않는다는 접근을 했는데 뭔가 이렇게 하면 나올 수 있는 답도 안나오는 거 아닌가 생각을 하였다.
   -> 그렇게 인터넷을 찾아보니 접근법은 비슷했다. 첫 전구에서 스위치를 켜는지 안켜는지의 경우에 내가 생각한 방법을 접목하면 답이 나온다는 것을 알 수 있었다.

첫 번째 전구를 키는지 안키는지의 두 가지 경우로 이후부터는 정답 형태와 비교하며 제일 앞쪽 전구를 바꿔야하는지 즉, i-1,i,i+1에서 i-1 전구의 상태를 바꿔야 하는지 아닌지를 기준으로 진행해가면 된다.

솔직히 그리디 알고리즘이라는 힌트를 보고도 정확히 느낌이 안와서 너무 헤맸던 것 같다. 관련 문제를 많이 접해봐야겠다.

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <deque>



using namespace std;

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0, 0, 1, -1 };



int N;
string orig;
string ans;
string tmp;

int minVal = 1e9;
int cnt = 0;

void lightOn(int i)
{
	if(i > 0)tmp[i - 1] = (tmp[i - 1] == '0') ? '1' : '0';


	tmp[i] = (tmp[i] == '0') ? '1' : '0';

	if (i < N-1)
		tmp[i + 1] = (tmp[i + 1] == '0') ? '1' : '0';
}

void solve(int first)
{
	tmp = orig;
	cnt = 0;

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

		for (size_t i = 1; i < N; i++)
		{
			if (tmp[i - 1] != ans[i - 1])
			{
				lightOn(i);
				cnt++;
			}
		
		}

		if (tmp == ans)
			minVal = min(minVal, cnt);
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	

	cin >> orig >> ans;

	solve(0);
	solve(1);

	if (minVal == 1e9)
		cout << -1;
	else
		cout << minVal;




	return 0;
}

<참고한 블로그>
min413
판교의 메타몽