[백준 2138]- 전구와 스위치(C++)[골드5]

문제

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

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

입력

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

출력

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

 

🔎문제 해석

스위치를 누르면 스위치 주변에 전구에 영향을 끼칩니다

특정한 패턴을 보이고 있습니다.

첫번째 스위치와 마지막 스위치를 제외한 스위치는 자신을 포함한 앞 뒤의 전구의 영향을 끼칩니다.

하지만 첫 번째 스위치를 누를 경우 자신을 포함한 뒤 전구의 영향을 끼치고,

마지막 스위치를 누를 경우 자신을 포함한 앞 전구의 영향을 끼칩니다.

 

 

그림이 참 못나네요. 아무튼 저런 식으로 전구들은 서로 영향을 주고 있습니다.

서로 영향을 주는 스위치를 특정할 수 있다면 굉장히 경우의 수가 줄어듭니다.

만약 첫번째첫 번째 스위치를 누르지 않는다면 첫 번째 전구에 영향을 주는 스위치는 2번째 스위치 하나로 특정할 수 있습니다.

 

하지만 만약 첫번째 스위치를 눌렀을 경우는 위에서 선택한 상황이랑은 달라집니다,

따라서 우리는 첫번째 스위치를 눌렀을 경우와, 누르지 않았을 경우 2가지를 생각해줘야 합니다.

 

스위치를 누르는데 이전 전구의 상태만 생각해 줍니다.
즉 2번째 스위치를 누를지 말지를 정하는 것은 1번째 전구의 상태가 우리가 만들려는 상태인지, 아닌지에 대한 여부입니다.
만들려는 상태와 다르다면 2번째 스위치를 누르고 , 1번째 전구의 상태는 우리가 만들려는 상태와 동일하게 될 것입니다.
즉 요점은 이전 전구의 상태를 보고 현재 단계의 스위치를 눌러준다입니다!

 

💻코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;
int n;
vector<int> fir;
vector<int> sec;
vector<int> temp;
int answer = INT_MAX,ans=0;
bool flag = true;
void light(int index);
bool funct();
int main()
{
    cin >> n;
    fir.resize(n, 0);
    temp.resize(n, 0);
    sec.resize(n, 0);
    for (int i = 0; i < n; i++)
    {
        scanf("%1d", &fir[i]);
        temp[i] = fir[i];
    }
    for (int i = 0; i < n; i++)
        scanf("%1d", &sec[i]);
    
    light(0); // 처음 스위치를 누른다.
    ans++; //스위치를 눌렀으므로, 누른 횟수를 +1 해줌.
    if (funct()) // 리턴값이 트루면 성공이라는 뜻이므로, 최소값을 갱신해줌.
        answer = min(answer, ans);
    else // 만들수 없을 떄
        flag = false;
    ans = 0;
    fir = temp; //기존 배열 다시 들고옴.
    if (funct()) //처음 스위치를 누르지 않는 경우
    {
        answer = min(answer, ans);
        flag = true;
    }
    if (flag == false) //만약 두 경우의 수를 통해서 만들수 없는 상태라면 -1을 출력, 아니면 최소횟수를 출력
        cout << -1 << endl;
    else
        cout << answer << endl;
}
void light(int index) //전구에 영향을 주는 함수. 첫,끝 스위치가 아니라면 index-1, index, index+1 모두 영향을 줌.
{
    if (index > 0)
    { // 첫 전구가 아니라면.
        if (fir[index - 1])
            fir[index - 1] = 0;
        else
            fir[index - 1] = 1;
    }
    if (index < n - 1)
    { // 끝전구가 아니라면
        if (fir[index + 1])
            fir[index + 1] = 0;
        else
            fir[index + 1] = 1;
    }
    if (fir[index])
        fir[index] = 0;
    else
        fir[index] = 1;
}
bool funct()
{ 
    for (int i = 1; i < n; i++)
    {
        if (fir[i - 1] != sec[i - 1])
        { //이전 상태가 결과물이랑 다르다면
            ans++;
            light(i);
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (fir[i] != sec[i]) // 다를 시.
            return false;
    }
    return true;
}

주석을  통해서 세부 코드는 이해해 주시길.. 🙏

 

😃느낀 점

• 이 문제는 접근방법이 어려워서 구글링을 참고했다.....
• 스위치를 눌러서 전구를 키는 함수가 굉장히 더러운 것 같다. 모쪼록 잘 이해하시길...