[백준/BOJ] 2138번 전구와 스위치 (C++)

www.acmicpc.net/problem/2138

2138번: 전구와 스위치

개인적으로 어려웠던 그리디 문제입니다. (다시 풀기)

문제에서 어떤 규칙이나 혹은 풀이 방향을 잡지 못해서 결국 검색을 통해 해결하였습니다. 포인트는 처음 전구를 바꾸는 경우와 바꾸지 않는 두가지 케이스로 나누는 것입니다. 각각의 케이스에서 1번째 전구부터 n-1개의 전구까지 현재 전구[i-1] 와 목표 전구[i-1] 를 비교하여 같은 경우는 그냥 넘어가고, 다른 경우는 0은 1로, 1은 0으로 바꿔주면 됩니다. 이런식으로 모든 비교가 끝나고, 현재 전구와 목표 전구를 비교하여 같으면 그대로 여태 전구를 변경한 수를 리턴하고, 같지 않으면 임의의 무한대 값을 넣어줍니다. 두 가지 케이스에서 각각 위의 과정을 마치고, 최소값을 answer 변수에 저장하고, 만약 answer가 임의의 무한대 값이라면 이는 불가능한 경우이므로 -1을 출력, 아니라면 그대로 answer를 출력합니다.

 

#include <iostream>
using namespace std;

void change(string &start, int idx) {
    for(int i = idx - 1; i <= idx + 1; i++) {
        if(i < 0 || i >= start.size()) continue;
        if(start[i] == '0') start[i] = '1';
        else start[i] = '0';
    }
}

int check(string start, string target, int n, bool state) { // 처음 전구 모양, 목표 전구 모양, 전구의 크기, 전구의 상태 
    int cnt = 0;
    
    // 처음 0번째 전구를 바꾸는 경우
    if(state) {
        change(start, 0);   
        cnt++;
    }
    
    // 1번째 전구부터 n-1번째 전구를 바꾸는 경우
    for(int i = 1; i < n; i++) {
        if(start[i - 1] != target[i - 1]) {
            change(start, i);
            cnt++;
        }
    }
    
    // 마지막으로 똑같은가 비교
    if(start != target) {
        cnt = 2147000000;
    }
    
    return cnt;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin>>n;
    string start, target;
    cin>>start>>target;
    
    int answer = min(check(start, target, n, false), check(start, target, n, true));
    answer == 2147000000 ? cout<<"-1" : cout<<answer;
}