전구와 스위치( BOJ 2138 )

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

2138번: 전구와 스위치

 

문제 파악하기

입력된 N개의 스위치를 적절하게 눌러서 우리가 원하는 상태로 바꿀 수 있는지, 만약 바꿀 수 있다면 눌러야 하는 스위치의 최소 횟수를 구하는 문제입니다. 만약 N의 값이 작다면 직접 모든 경우의 수를 확인할 수 있지만 N이 최대 100,000이기 때문에 좀 더 효율적인 알고리즘이 필요합니다. 다행히 스위치는 항상 바로 왼쪽과 오른쪽에 위치한 전구에만 영향을 미치기 때문에 이 점을 활용하면 문제를 해결할 수 있습니다.

 

문제 해결하기

만약, 어떤 전구의 상태를 바꾸고 싶다면 현재 전구의 오른쪽에 위치한 스위치를 누르면 됩니다. 이 점이 바로 문제를 해결하는데 핵심적인 개념입니다. 탐색을 왼쪽에서 오른쪽 방향으로 진행하면서 현재 스위치의 왼쪽에 위치한 전구의 상태를 확인하고, 만약 바꿔야 한다면 현재 스위치를 눌러 상태를 바꿔주면 됩니다. 탐색이 왼쪽에서 오른쪽으로 진행되기 때문에 이전에 탐색했던 값에 영향을 끼치지 않으려면 항상 상태를 바꿀 전구의 오른쪽 스위치를 눌러야 합니다. 예를 들어 [ 010100 ]의 상태를 [ 001000 ]으로 바꾸고자 합니다. 이 경우, 두 번째 전구의 상태가 다르다고 두 번째 스위치를 누르기 보다는 세 번째 전구의 스위치를 눌러 한 번에 원하는 상태로 바꿀 수 있습니다.

 

010100 >> (3번째 스위치) >> 001000

 

이렇게 상태가 다른 전구들을 확인해서 쭉 바꾼 다음, 맨 마지막 전구의 상태를 확인하면 우리는 원하는 목표 상태로 만들었는지 여부를 확인할 수 있습니다. 다만, 문제는 첫 번째 전구입니다. 첫 번째 전구가 예외사항이라면 예외사항이라고 할 수 있는데 그 이유는 첫 번째 전구의 상태를 바꾸는 방법이 다른 전구들과 달리 한 가지 더 있기 때문입니다. 바로, 첫 번째 스위치를 누르는 것입니다. 첫 번째 전구는 맨 왼쪽에 있기 때문에 왼쪽에 상태가 바뀔 전구가 없습니다. 그렇기에 우리는 첫 번째 스위치를 누르는 경우와 누르지 않는 경우 2가지를 모두 확인한 다음, 가장 적은 횟수를 구하면 됩니다. 참고로 시작 상태가 주어지면 나올 수 있는 결과는 1가지이기 때문에 전체 알고리즘의 시간 복잡도는 O(N)이 됩니다.

 

소스코드

#include <iostream>
#define INF 987654321
using namespace std;
 
int N, ret;
string bef, aft, str;
 
int check(string s) {
    int cnt;
    
    cnt = 0;
    for(int i=1;i<N;i++) {
        if(s[i-1] == 0) continue;
        
        // 동전 뒤집기
        cnt++;
        for(int j=-1;j<=1;j++) s[i+j] = 1-s[i+j];
    }
 
    // 불가능한 경우 확인
    if(s.back() == 1) cnt = INF;
    
    return cnt;
}
 
int main() {
    cin >> N;
    cin >> bef;
    cin >> aft;
    for(int i=0;i<N;i++) str.push_back(bef[i]!=aft[i]);
 
    // 첫 번째 동전 뒤집지 않기
    ret = check(str);
 
    // 첫 번째 동전 뒤집기
    for(int j=0;j<2;j++) str[j] = 1-str[j];
    ret = min( ret, check(str)+1 );
 
    // 출력
    if(ret == INF) cout << "-1";
    else cout << ret;
}
 

후기

USACO에서 출제되었던 사발뒤집기(http://koistudy.net/?mid=prob_page&NO=211&SEARCH=0)문제의 심화 문제입니다. 전구 관련 문제들의 특징이라고 할 수 있는 왼쪽 혹은 위쪽 상태 바꾸기의 대표적인 사례라고 할 수 있습니다. 개인적으로 이 문제는 감회가 새로운데, 2015년도 우연한 기회로 정올 멘토링 특강에 참여해 수업을 들었을 때 소개받은 문제입니다. 그 당시에는 알고리즘을 공부하지 않아 정말 어려웠던 문제인데 이제는 스스로 풀 수 있다는 점에서 더욱 재미있던 문제였습니다.