백준 2138 - 전구와 스위치

문제 설명

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

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

https://www.acmicpc.net/problem/2138

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 시작상태에서 스위치를 켜 최종상태로 만들 때, 최소한의 스위치를 켜는 횟수를 구하는 것이다.

스위치를 키면, 왼쪽, 가운데, 오른쪽 스위치가 변한다.

만약, 끝쪽(0 혹은 N) 일 경우엔 무시한다.

 

문제의 접근법은 그리디를 이용해 최적의 상태를 만들어 나가는 것이다.

최적의 상태란 현재 idx 이전의 전구는 모두 최종상태와 일치하는 것을 의미한다.

이 가정이 성립하는 이유는 idx번째 스위치를 켜면 적용되는 범위가 [idx-1, idx, idx+1]이기 때문이다.

즉, idx-1의 전구를 올바른 상태로 유지하며 진행한다면 최종상태에 도착할 수 있다는 뜻이 된다.

한 가지 주의할 점은 0번 전구를 켜냐 안 켜냐에 따라 결과가 달라진다.

0번 전구는 이전 전구가 없기 때문에 선택지가 생긴다.

다른 말로하면, 1번 전구를 켜기 시작할 때, 0번 전구가 최종상태와 일치하는지 아닌지로 갈릴 수 있다는 뜻이다.

따라서, 0번을 켜고 시작하는 경우, 0번을 건들지 않고 1번부터 시작하는 경우 두 가지 경우를 모두 살펴본 뒤 최솟값을 구하면 된다.

우선, 스위치를 켜는 함수이다.

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

[idx-1, idx, idx+1] 번째 전구의 상태를 변경한다.

idx-1은 0이하로 내려가는 경우가 없기 때문에 예외처리를 하지 않았다.

 

다음은, 스위치를 켜며 전구의 상태를 맞춰가는 함수이다.

void solve(int startIdx)
{
    current = start;
    int cnt = 0;

    if (startIdx == 0)
    {
        current[0] = current[0] == '0' ? '1' : '0';
        current[1] = current[1] == '0' ? '1' : '0';
        cnt++;
    }

    for (int i = 1; i < N; i++)
    {
        if (current[i - 1] != target[i - 1])
        {
            lightOn(i);
            cnt++;
        }
    }

    if (current == target) ans = min(ans, cnt);
}

0에서 시작한 경우 0번 스위치를 변경하여 전구의 상태를 변경한 뒤 시작한다.

1번 전구부터 이전 전구가 최종상태와 일치하지 않을 경우 스위치를 켠 뒤 조작 횟수를 올린다.

 

모든 연산이 종료된 후, 최종 상태와 현재의 전구의 상태가 일치하면 정답을 갱신한다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N;
string start, target, current;
int ans = INT_MAX;

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

void solve(int startIdx)
{
    current = start;
    int cnt = 0;

    if (startIdx == 0)
    {
        current[0] = current[0] == '0' ? '1' : '0';
        current[1] = current[1] == '0' ? '1' : '0';
        cnt++;
    }

    for (int i = 1; i < N; i++)
    {
        if (current[i - 1] != target[i - 1])
        {
            lightOn(i);
            cnt++;
        }
    }

    if (current == target) ans = min(ans, cnt);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    cin >> start >> target;

    solve(0);
    solve(1);

    if (ans == INT_MAX) cout << -1;
    else cout << ans;

    return 0;
}

---