백준 2138 / C++ / 그리디준 2138 / C++ / 그리디

 

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int n;
vector<bool> initial, target;

// 스위치를 누르는 함수
void pressSwitch(vector<bool>& bulbs, int index) {
    if (index > 0) bulbs[index - 1] = !bulbs[index - 1];
    bulbs[index] = !bulbs[index];
    if (index < n - 1) bulbs[index + 1] = !bulbs[index + 1];
}

// 전구를 바꾸는 함수 (첫 번째 전구를 누를지 여부 선택 가능)
int solve(bool pressFirst) {
    vector<bool> bulbs = initial;
    int count = 0;

    // 첫 번째 전구를 누르는 경우
    if (pressFirst) {
        pressSwitch(bulbs, 0);
        count++;
    }

    // 앞에서부터 필요한 곳만 스위치 누르기
    for (int i = 1; i < n; i++) {
        if (bulbs[i - 1] != target[i - 1]) {
            pressSwitch(bulbs, i);
            count++;
        }
    }

    // 결과 확인
    if (bulbs == target) return count;
    return INT_MAX;  // 불가능한 경우
}

int main() {
    cin >> n;
    initial.resize(n);
    target.resize(n);

    // 초기 전구 상태 입력
    for (int i = 0; i < n; i++) {
        char ch;
        cin >> ch;
        initial[i] = (ch == '1');
    }

    // 목표 전구 상태 입력
    for (int i = 0; i < n; i++) {
        char ch;
        cin >> ch;
        target[i] = (ch == '1');
    }

    // 두 가지 경우 비교
    int result = min(solve(false), solve(true));

    // 정답 출력
    if (result == INT_MAX) cout << -1;
    else cout << result;
}

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

이 문제를 풀 때 나는 현재 스위치를 기준으로 나와 양옆이 다르면 스위치를 누르려했으나 그게 아니었다 그냥 앞에서 부터 보면서 스위치를 기준으로 이전 전구가 다르면 스위치를 누르는데 0번스위치부터 할건지 1번스위치 부터 누를건지 2개의 경우의 수를 구해서 그중 최솟 값을 구하면 되는 거였다 0번스위치와 1번스위치로 나눈 이유는 0번 스위치의 값을 결정 할수 있는경우 지금 누르거나 다음에 누르거나 두가지 경우의수밖에없기 때문에 우리는 이전 상태를 비교함으로 0번스위치가 1일때의 시작과 0일때의 시작을 모두 비교해보는 것이다