[알고리즘] 방탈출 (boj_15729)

문제

방탈출 게임을 하던 혜민이는 마지막 문제에 봉착했다. 단서는 다음과 같다. 앞에는 일렬로 놓여진 N개의 버튼이 모두 불이 꺼진 상태로 있다.

1. 0 또는 1로 구성되어 있는 N자리 수가 적힌 쪽지가 있다.
2. 0은 불이 꺼진 버튼, 1은 불이 켜진 버튼을 뜻한다.
3. 불이 켜져 있는 버튼을 누르면 불이 꺼지고, 불이 꺼져 있는 버튼을 누르면 불이 켜진다.
4. 버튼을 누르면 그 버튼 뿐만이 아닌 오른쪽 두 개의 버튼도 같이 눌린다. 혜민이는 현재 모두 불이 꺼진 상태에서 버튼을 최소로 눌러서 쪽지와 똑같은 상태로 만들어야 한다는 것을 알아냈다! 혜민이를 도와줘서 방탈출 게임에 성공하자.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000)가 주어지고 둘째 줄에는 쪽지에 적혀 있는 N자리의 수가 빈 칸을 사이에 두고 주어진다.

출력

눌러야하는 버튼의 최솟값을 출력한다.

흐름

• 감이 오질 않아서 풀이를 보았다.
• 원하는 나열을 모두 0으로 만든다고 생각한다.
• 왼쪽에서부터 1을 만나면 순차적으로 0으로 (i+1, i+2는 값을 바꿔줌) 바꿔준다.

알아두면 좋을 사항

#include <algorithm>
copy(src_arr, src_arr+N, dst_arr); // src_arr 배열에 든 값 dst_arr로 복사

#include <iostream>
#include<algorithm>

using namespace std;


int main(void)
{
    int N;
    cin>>N;
    int arr[1000000] = {0,};
    for(int i =0;i<N;i++)
    {
        cin>>arr[i];
    }
    int count = 0;

    for(int i=0; i<N;i++)
    {
        if(arr[i] == 1)
        {

            arr[i] = !arr[i];
            arr[i+1] = !arr[i+1];
            arr[i+2] = !arr[i+2];
            count++;
        }
    }
    cout<<count;
}