[Algorithm] Baekjoon 2138번 : 전구와 스위치

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

2138번: 전구와 스위치

#define MAX_NUM 1000000000
 
 
char switchOn(char temp)
{
    if (temp == '0') return '1';
    return '0';
}
 
int solution(bool check, string start, string target)
{
    int count = 0;
 
    if (check) // 0번째꺼 카운팅.
    {
        start[0] = switchOn(start[0]);
        start[1] = switchOn(start[1]);
        ++count;
    }
 
    for (int i = 1; i < target.size(); ++i)
    {
        if (start[i - 1] == target[i - 1])
        {
            continue;
        }
        else
        {
            ++count;
            start[i - 1] = switchOn(start[i - 1]);
            start[i] = switchOn(start[i]);
 
            if (i + 1 != target.size()) // n번째 인덱스(마지막 인덱스)에선 범위 넘어서니까 수행하면 안됨.
            {
                start[i + 1] = switchOn(start[i + 1]);
            }
        }
    }
 
    if (start != target) return MAX_NUM;
    return count;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    string start;
    string target;
    int answer = MAX_NUM;
 
    cin >> n;
    cin >> start >> target;
 
    answer = min(answer, solution(false, start, target));
    answer = min(answer, solution(true, start, target));
 
    if (answer == MAX_NUM)
    {
        cout << -1;
        return 0;
    }
 
    cout << answer;
}

 

특정 스위치를 키면 양옆의 스위치도 같이 반전된다는 조건때문에 뭔가 처음 접하면 어떻게 접근해야할지 알기 힘든 문제..

사실 앞에서부터 차근차근 체크하면서 풀 수 있는 문제이다. 

 

먼저 전체적인 해설은 이 글을 보면 좋다.

https://staticvoidlife.tistory.com/143

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

 

0번째 스위치를 키고 로직을 수행한 경우와 키지않고 수행한 경우, 두 경우를 고려해야 하는 이유는 다음과 같다.

0번째 스위치를 키고 안키고의 차이는, 1번째전구를 뭘로 시작하냐의 차이이다.

0번째 스위치를 킨다면, 1번째전구는 반전된 상태에서 로직이 시작될것이고, 안킨다면 기존값 그대로 로직을 수행하게 된다.

예를들어  00000 -> 00100으로 해야한다고 가정한다. 0번째를 안키고 수행하면 00000에서 로직을 수행하게된다.

0번째를 킨다면 11000이 되고 여기서부터 로직을 수행한다.

 

로직만 고려해봤을 때는 0번쨰가 0이든 1이든, 어차피 i+1번째에서 검사 후 i+1번쨰 스위치를 킴으로써 i번쨰를 바꿔줄 수 있기 때문에 0이든 1이든 상관없을 것 같이 보인다.

하지만 문제는 0번째를 바꾸기위해서는 1번째 스위치를 켜야하고, 그러면 0번째뿐만 아니라 1번째, 2번째 전구까지 반전을 시켜야 한다. 

결국 1번째, 2번째 전구도 뒤에서 검사해서 바꾸면 되지 않나? 싶지만 인덱스에도 끝은 있다.

결국 맨 끝의 전구는 그 다음 스위치가 없기 때문에 바꿀 수 없다!

 

그렇기 때문에 0번째 '스위치'를 키던가 그대로 두던가 하는 두가지를 모두 고려해야 한다.

 

말로하니까 어렵지 그냥

 

00000으로 시작하는거랑

11000으로 시작하는거랑 다르다는걸 인지하면 된다.