백준 2138 전구와 스위치

백준 2138 전구와 스위치

2138번: 전구와 스위치

 

질문보기 해서 겨우 풀었다.

1번째 스위치를 제외하고 풀면 n-1번째 전구는 n번째 스위치를 누를때 최종상태가 결정된다.

그러므로 n번째 n-1번째 전구가 만들고자 하는 전구 상태와 다르면 스위치를 눌러주면 되는것이다.

마지막까지 다가서 맨 마지막 스위치가 만들고자 하는 전구 상태와 같으면 같은 것이다.

(상태가 0과 1일때 그냥 1-bt[i]해주면 1은 0으로 0은 1로 바뀜)

여기서 문제는 1번째 스위친데  

1번째 스위치를 켰을때랑 안켰을때 전부 만들고자 하는 전구상태로 갈 수도 있으므로

1번째 스위치를 켰을때랑 안켰을때 이 두가지 경우로 나눠서 답을 찾아줘야했다.

그 둘중에 작은 것이 정답

​

그리고 입력을 공백없이 받는 경우 문자열로 입력을 받는 방법도 있지만 나는 귀찮아서

그냥 cstdio헤더 선언해주고 scanf("%1d",&bt[i]); 이렇게 받았다.​

 

 

#include <iostream>
#include <cstdio>
​
using namespace std;
​
int bt[100001];
int temp[100001];
int result[100001];
int cnt = 0;
​
bool compare(int a[],int n)
{
    for (int i = 1; i <= n; ++i) {
        if (a[i] != result[i])
            return false;
    }
    return true;
}
​
void change(int a[],int sw,int n)
{
    for (int j = -1; j < 2; ++j) {
        if(sw+j>0&&sw+j<=n)
            a[sw + j] = 1 - a[sw + j];
    }
    cnt++;
}
​
int main(void)
{
    int n;
    cin >> n;
​
​
    for (int i = 1; i <= n; ++i) {
        scanf("%1d", &bt[i]);
        temp[i] = bt[i];
    }
​
    for (int i = 1; i <= n; ++i) {
        scanf("%1d", &result[i]);
    }
​
    //temp는 1눌렀을때
    //bt는 1안눌렀을때
    
    change(temp, 1, n);
​
    int tcnt = 1;
    int bcnt = 0;
    for (int i = 2; i <= n; ++i) {
        if (temp[i - 1] != result[i - 1]) {
            change(temp, i, n);
            tcnt++;
        }
        if (bt[i - 1] != result[i - 1]) {
            change(bt, i, n);
            bcnt++;
        }
    }
​
    int ans = -1;
    if (compare(temp, n))
        ans = tcnt;
    else if (compare(bt, n))
        ans = bcnt;
​
    if (compare(temp, n) == true && compare(bt, n)==true)
        ans = tcnt < bcnt ? tcnt : bcnt;
​
​
    cout << ans << endl;
​
    return 0;
}​