백준 2138번 전구와 스위치 (C++)

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

2138번: 전구와 스위치

문제 요약

 

1. 전구들이 n개 나열되어있다.

2. n번째 전구의 전원을 누르면 n-1, n, n+1은 각각 원래 상태에서 반대 상태로 전환된다. (ex : 0 -> 1)

3. 첫 번째 전구의 전원을 누르면 1, 2번째만 상태가 바뀌고, 마지막 전구의 전원을 누르면 n-1, n번째만 상태가 바뀐다.

4. 전구의 숫자 n개, 최초의 전구 상태, 목표 전구 상태가 주어졌을 때, 목표 전구 상태를 달성하기 위해 최소한의 스위치 누름 횟수를 출력하라.

5. 정답을 구할 수 없는 경우 -1을 출력하라.

 

핵심 포인트

 

전구의 최대 개수는 100,000이므로, 2중 for문을 활용해 BruteForce로 접근했다간 시간초과가 발생합니다.

때문에 Greedy로 접근해 for문을 한 번만 돌려야지 시간초과가 발생하지 않습니다.

 

또한 한 번 체크한 전구를 두번 체크 하지 않기 위해서는 아래 특징을 잘 이해해야 합니다.

n번째 전구의 전원을 누르면 n-1, n, n+1은 각각 원래 상태에서 반대 상태로 전환

 

n번째 전구의 상태를 전환하기 위해서, 동시에 for문을 한 번만 돌리기 위해서는 n번째 전구가 아닌 n+1번째 전구의 스위치를 누르면 됩니다.

 

다만 이러한 조건에 영향을 끼치는 변수는 첫 번째 전구 입니다.

첫 번재 전구를 눌러서 1번, 2번 전구가 켜짐

두 번째 전구를 눌러서 1,2,3번 전구가 켜짐

첫 번째 전구를 키느냐 마느냐에 따라 최소 한의 스위치 누름 횟수, 나아가서 목표 전구의 도달 여부가 달라질 수 있습니다. 때문에 다음과 같은 두 케이스를 구해서 목표 전구 상태에 도달할 수 있는지, 나아가서 최소 버튼 누름 횟수를 구합니다. 

 

1. 첫 번째 전구를 누르고 시작하는 경우
2. 첫 번째 전구를 누르지 않고 시작하는 경우

문제 풀이

 

1. 필요한 변수들을 선언하고 값을 입력 받습니다. 편의상 변수들은 전역변수로 선언했습니다.

#define MAX 987654321

int n, ans = MAX, cnt = 0;
string st, dt, temp;

...

void input() { // int main()내부에서 호출
    cin >> n;
    cin >> st;
    cin >> dt;
}

 

2. 다음은 스위치를 키는 함수들입니다.

solve(0)일 경우 첫 번째 전구를 키고 시작하며, solve(1)일 경우, 첫 번째 전구를 키지 않습니다.

void lightOn(int idx) { // 1
    if (idx > 0) temp[idx - 1] = (temp[idx - 1] == '0') ? '1' : '0';
    temp[idx] = (temp[idx] == '0') ? '1' : '0';
    if (idx < n - 1) temp[idx + 1] = (temp[idx + 1] == '0') ? '1' : '0';
}

void solve(int first) { // int main()내부에서 호출
    temp = st;
    cnt = 0;
    if (first == 0) { // 2
        temp[0] = (temp[0] == '0') ? '1' : '0';
        temp[1] = (temp[1] == '0') ? '1' : '0';
        cnt++;
    }
    for (int i = 1; i < n; i++) { // 3
        if (temp[i - 1] != dt[i - 1]) {
            lightOn(i);
            cnt++;
        }
    }
    if (temp == dt) ans = min(ans, cnt); // 4
}

(1) 전구의 상태를 변화하는 코드입니다. 만약 해당 전구가 첫 번째 인지, n 번째인지 까지 고려하여 코드를 작성합니다.

(2) 첫 번째 전구를 키고 시작하는 경우를 위한 코드입니다.

(3) 전구를 하나씩 키는 코드입니다. i는 1부터 시작한다는 점이 특징입니다.

또한 n번째 전구가 아닌 n-1번째 전구가 목표 전구와 동일한지 아닌지에 따라 전구를 키고 끕니다.

(4) 만약 전구를 킨 횟수가 ans보다 작을 경우에 ans를 새로 갱신합니다.

 

3. 전반적인 main함수 내부입니다.

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input(); // 1
    solve(0); // 2
    solve(1); // 3
    if (ans != MAX) cout << ans << "\n"; // 4
    else cout << -1 << "\n"; // 5
    return 0;
}

(1) 1번에서 언급된 변수 입력 함수입니다.

(2) 첫 번째 전구를 키고 시작하는 코드입니다.

(3) 첫 번째 코드를 키지 않고 시작하는 코드입니다.

(4) 만약 ans의 값이 새로 갱신되었다면 해당 ans를 출력하면 됩니다.

(5) 그렇지 않을 경우 목표 전구에 도달하지 못한다는 뜻이므로, -1을 출력하고 종료합니다.

 

#include <iostream>
#include <algorithm>
#define MAX 987654321

using namespace std;

int n,ans=MAX,cnt=0;
string st, dt, temp;

void input(){
    cin >> n;
    cin >> st;
    cin >> dt;
}

void lightOn(int idx){
    if(idx>0) temp[idx-1] = (temp[idx-1]=='0') ? '1' : '0';
    temp[idx] = (temp[idx]=='0') ? '1' : '0';
    if(idx<n-1) temp[idx+1] = (temp[idx+1]=='0') ? '1' : '0';
}

void solve(int first){
    temp = st;
    cnt = 0;
    if(first==0){
        temp[0] = (temp[0]=='0') ? '1' : '0';
        temp[1] = (temp[1]=='0') ? '1' : '0';
        cnt++;
    }
    for(int i=1; i<n; i++){
        if(temp[i-1]!=dt[i-1]){
            lightOn(i);
            cnt++;
        }
    }
    if(temp==dt) ans = min(ans,cnt);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve(0);
    solve(1);
    if(ans!=MAX) cout << ans << "\n";
    else cout << -1 << "\n";
    return 0;
}