백준 2138번 : 전구와 스위치

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

2138번: 전구와 스위치

 

 

 문제설명 

 

1. 첫번째 줄부터 전구의 갯수, 현재 전구의 상태, 원하는 전구의 상태가 주어짐

2. 전구와 스위치는 각각 N개씩있고 만약 i번째 스위치를 누른다면 i-1,i,i+1 번째 전구의 상태가 바뀐다.

3. 현재 전구의 상태에서 원하는 전구의 상태로 바꾸기위한 스위치 동작의 최소 횟수 출력.

 

 

 알고리즘 

 

1. 너무나 당연히 , 스위치를 누르거나 안누르거나 의 두가지 경우로 재귀를 돌리면 시간 초과가 발생한다 ^^ ..

2. 그래서 스위치를 가능한 그리디 하게 눌러줘야됨 .

3. i번째 전구의 상태에 마지막으로 영향을 미치는 스위치는 i+1번째 스위치이다. 이것을 이용하여 만약 i-1 번째  전구가

  목표로하는 전구의 상태가 아니면 누르는 식으로 재귀 함수를 진행 시킨다.

 

4. 주의할점은 첫번째 전구는 누르는 경우와 누르지않는 경우 두가지경우로 진행 시킨다.

 

 코드 

 

#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
 
 
const int INF = 987654321; 
 
int N, answer;
 
string s, copyS, result; 
 
//스위치 누르는 함수
void push(int idx)
{
        if (idx > 0)
                 copyS[idx - 1] = (copyS[idx - 1] == '0') ? '1' : '0';
        
        copyS[idx] = (copyS[idx] == '0') ? '1' : '0';
 
        if (idx < N - 1)
                 copyS[idx + 1] = (copyS[idx + 1] == '0') ? '1' : '0';
}
 
 
 
void simulation(int idx, int cnt)
{
 
        if (idx == N - 1)
 
        {
 
                 //같은지 확인
 
                 bool flag = true;
 
                 for(int i=0; i<copyS.length(); i++)
 
                         if (copyS[i] != result[i])
 
                         {
 
                                 flag = false;
 
                                 break;
 
                         }
 
                 if (flag)
 
                         answer = min(answer, cnt);
 
                 //스위치를 눌러보고 다시 확인
 
                 push(idx);
 
                 flag = true;
 
                 for (int i = 0; i<copyS.length(); i++)
 
                         if (copyS[i] != result[i])
 
                         {
 
                                 flag = false;
 
                                 break;
 
                         }
 
                 if (flag)
 
                         answer = min(answer, cnt + 1);
 
                 return;
 
        }
 
       
 
        //스위치를 안 누른 상태
 
        if (copyS[idx - 1] == result[idx - 1])
 
                 simulation(idx + 1, cnt);
 
        //스위치를 누르고
 
        push(idx);
 
        if (copyS[idx - 1] == result[idx - 1])
 
                 simulation(idx + 1, cnt + 1);
 
        //원상복귀
 
        push(idx);
 
}
 
 
 
int main(void)
 
{
 
        ios_base::sync_with_stdio(0);
 
        cin.tie(0);
 
        cin >> N >> s >> result;
 
       
 
        answer = INF;
 
        //0번째 스위치를 누르지 않은 상태에서 시작
 
        copyS = s;
 
        simulation(1, 0);
 
       
 
        //0번째 스위치를 누른 상태에서 시작
 
        copyS = s;
 
        push(0);
 
        simulation(1, 1);
 
        if (answer == INF)
 
                 cout << -1 << "\n";
 
        else
 
                 cout << answer << "\n";
 
        return 0;
 
}