0과 1로 구성된 배열이 주어지며, 각 값은 순서대로 하나의 회선에 연결된 전구의 상태를 나타냅니다. 0은 전구가 꺼져 있음(OFF)을, 1은 켜져 있음(ON)을 의미합니다.
N개의 전구로 이루어진 시퀀스에서 i번째 전구의 스위치를 누르면, 그 오른쪽에 있는 모든 전구(i+1번째부터 n번째까지)의 상태가 반전됩니다. 즉, 켜져 있던 전구는 꺼지고 꺼져 있던 전구는 켜집니다.
목표는 주어진 전구 상태에서 모든 전구를 켜기 위해 눌러야 하는 최소 스위치 횟수를 구하는 것입니다. 단, 같은 스위치는 몇 번이든 다시 누를 수 있습니다. 이는 배열에서 오른쪽 인덱스 값들을 뒤집어(flipping) 모두 1로 설정하는 문제와 동일합니다.
입력 · 출력 예시
예시 1
Bulbs[] = { 1, 0, 1, 0 }
출력:
Minimum right flips: 3
풀이 과정: 초기 상태는 1010입니다.
2번 스위치 클릭 → 1:101 (뒤집기 횟수 = 1) 3번 스위치 클릭 → 11:10 (뒤집기 횟수 = 2) 4번 스위치 클릭 → 111:1 (뒤집기 횟수 = 3)
예시 2
Bulbs[] = { 1, 0, 0, 0 }
출력:
Minimum right flips: 1
풀이 과정: 초기 상태는 1000입니다.
2번 스위치 클릭 → 1:111 (뒤집기 횟수 = 1)
스위치를 한 번만 눌렀을 뿐인데 오른쪽의 모든 전구가 한꺼번에 켜진 것을 확인할 수 있습니다.
접근 방법
- 정수 배열에 N개 전구의 상태가 저장되어 있습니다.
minFlips(int arr[], int n)함수는 배열과 그 길이 n을 입력받아, 배열의 모든 값을 1로 만들기 위해 필요한 최소 오른쪽 뒤집기 횟수를 반환합니다.- 변수
count는 지금까지 누른 스위치(뒤집기) 횟수를 저장하며, 초기값은 0입니다. - 핵심 아이디어는 스위치를 누를 때마다 오른쪽 전구 전체가 반전된다는 점입니다. 따라서 왼쪽부터 차례대로 살펴보면서, 지금까지 스위치를 누른 횟수가 홀수인지 짝수인지만 추적하면 됩니다.
- 각 위치에서 누적된 뒤집기를 반영한 실제 전구 상태가 꺼져 있으면(0이라면) 스위치를 누르고(count 증가) 뒤집기 상태를 반전시킵니다. 이미 켜져 있다면 아무 작업도 하지 않습니다.
- 배열을 끝까지 탐색한 후 count에 저장된 값을 결과로 반환합니다.
C++ 구현 예시
// C++ 프로그램: 배열의 모든 값을 1로 만들기 위한
// 최소 오른쪽 뒤집기 횟수를 계산합니다.
#include <bits/stdc++.h>
using namespace std;
// 최소 뒤집기 횟수를 계산하는 함수
int minFlips(int arr[], int n){
int count = 0;
bool flipped = false; // 스위치를 누른 횟수가 홀수인지 여부
for(int i = 0; i < n; i++){
// 누적된 뒤집기를 반영한 실제 전구 상태
int state = arr[i] ^ (flipped ? 1 : 0);
if(state == 0){ // 전구가 꺼져 있다면
count++; // 스위치를 누르고
flipped = !flipped; // 뒤집기 상태 갱신
}
}
return count;
}
int main(){
int Arr[] = {0, 1, 0, 1};
int N = 4;
cout << "배열의 모든 값을 1로 설정하기 위한 최소 오른쪽 뒤집기 횟수: "
<< minFlips(Arr, N);
return 0;
}
출력
배열의 모든 값을 1로 설정하기 위한 최소 오른쪽 뒤집기 횟수: 4
마무리
이 문제의 핵심은 스위치를 누를 때마다 실제로 배열 전체를 뒤집는 대신, 누른 횟수의 홀짝성(parity)만 추적하면 된다는 점입니다. 이렇게 하면 불필요한 배열 조작 없이 O(n) 시간 복잡도로 정답을 구할 수 있어 매우 효율적입니다.