[BOJ] 2138 : 전구와 스위치 C++

문제

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1<i<N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(2≤N≤100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다.

 

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

 

예제 입력 1	예제 출력 1
3 000 010	3

 

CODE

#include <bits/stdc++.h>

using namespace std;

void switching(vector<int>& state, int idx) // idx-1, idx, idx+1의 세 개의 전구의 상태가 바뀜
{
    for(int i = idx - 1; i <= idx + 1; i++)
    {
        if(i < state.size())
            state[i] = !state[i];
    }
}

int solve(vector<int> state, vector<int>& target, int ans)
{
    int size = state.size();
    for(int i = 0; i < size - 1; i++)
    {
        if(state[i] != target[i])
        {
            ans += 1;
            switching(state, i + 1); // i번째 상태가 일치하지 않다면 i+1번 스위치를 누름
        }
    }
    if(state[size - 1] == target[size - 1]) // 상태 모두 일치
        return ans;
    else 
        return -1;
}

int main()
{
    int N;
    scanf("%d", &N);
    vector<int> state(N);
    vector<int> target(N);

    for(int i = 0; i < N; i++)
        scanf("%1d", &state[i]);
    for(int i = 0; i < N; i++)
        scanf("%1d", &target[i]);

    int ans1 = solve(state, target, 0); // 첫 번째 스위치를 안누른 상태
    state[0] = !state[0], state[1] = !state[1]; 
    int ans2 = solve(state, target, 1); // 첫 번째 스위치를 누른 상태

    if(ans1 == -1 && ans2 == -1) cout << -1;
    else if(ans1 != -1) cout << ans1;
    else if(ans2 != -1) cout << ans2;
    else cout << min(ans1, ans2);

}

 

COMMENT

BOJ 1080 : 행렬 문제와 비슷한 문제다. 다만 행렬 문제는 항상 3 X 3 크기의 부분행렬을 뒤집지만 이 문제는 스위치를 누르는 행위가 전구 3개의 상태를 변화시킬수도, 2개의 상태를 변화시킬 수도 있다는 것이 차이점이다. 

 

 i번째 스위치를 누르는 것을 switching(i)라 하자.

   1. 어떤 스위치부터 누르는가, 즉 스위치를 누르는 순서는 결과에 영향이 없다.

   2. 0번째 스위치를 누른다면 예외적으로 전구 2개의 상태를 변화시키므로, 누른 경우와 누르지 않은 경우를 모두 다 따져봐야 한다.

     - 0번째 스위치를 누를지 안누를지 정했다면, 0번째 상태를 변화시키는 방법은 switching(1)뿐이다.

     - 계속해서, stateA[i]과 target[i]가 다르다면 동일하게 만드는 방법 또한 swithcing(i+1)뿐이다.

   3. 0 ~ size-2 번째 까지의 상태를 동일하게 만들었다고 가정하자.

     - size-1번째 상태까지 같다면 스위치를 두번 누르는 행위는 의미가 없으므로 이전까지 스위치를 누른 횟수가 최솟값

     - size-1번째 상태가 다르다면 답을 정할 수 없는데, 이 스위치를 눌러 size-1번째의 상태를 같게 만든다면 size-2번째 상태가 달라지기 때문이다.

     - 따라서 0번째 스위치를 눌렀을 때의 최솟값과 누르지 않았을 때의 최솟값 중 최솟값이 문제의 답이 된다.

 

도움이 되셨다면 공감 꾸욱! 부탁드립니다 ~~!!😊