백준 2138번 전구와 스위치

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

재미있는 그리디 문제였습니다.

N은 최대 100,000이기 때문에 단순 재귀 호출을 통해 풀려고 한다면 메모리초과가 발생합니다.

따라서, 그리디하게 접근해야합니다.

알고리즘은 아래와 같습니다.

1. 0번째 스위치를 누르지 않고 시작하는 경우와 0번째 스위치를 누르고 시작하는 경우로 나눕니다.

2. 모든 경우를 재귀 호출하는 경우 메모리 초과가 나기 때문에 보고 있는 인덱스 직전의 전구 상태를 봅니다.

- 인덱스를 한번 지나가면 다시 돌아오지 않기 때문에 확인하고 있는 (인덱스 - 1)에 위치한 전구의 상태를 보고 누를지 말지 결정합니다.

a) (인덱스 - 1)에 위치한 전구의 상태와 만들고자하는 배열의 (인덱스 - 1)에 위치한 전구의 상태가 동일하다면 스위치를 누르지 말고 다음 인덱스로 재귀호출합니다.

b) a)가 성립하지 않는다면 스위치를 누르고 재귀호출합니다.

3. 인덱스가 N-1에 도착하면 마지막 전구를 확인하는 것이기 때문에 두 가지 경우로 나눕니다.

i) 스위치를 누르지 않은 상태에서 만들고자하는 전구의 배열과 동일한지 확인합니다.

ii) 스위치를 누른 뒤 상태에서 만들고자하는 전구의 배열과 동일한지 확인합니다.

iii) i) 이나 ii)가 성립한다면 결과 값을 최신화시켜줍니다.

#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;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~