우리는 동일한 와이어로 순서대로 연결된 전구의 상태를 나타내는 0과 1의 배열이 제공됩니다. 0은 전구가 꺼져 있음을 나타내고 1은 전구가 켜져 있음을 나타냅니다. N 전구의 이러한 시퀀스에 대해 전구의 스위치를 누르면 오른쪽의 모든 전구(i+1에서 n까지)가 ON에서 OFF로 또는 OFF에서 ON으로 이전 응시를 변경합니다.
모든 전구의 주어진 상태에 대해 목표는 모든 전구를 켜기 위해 눌러야 하는 최소 스위치를 찾는 것입니다. [ 같은 스위치를 여러 번 누를 수 있음 ]. 배열에서 오른쪽 인덱스 값의 상태를 뒤집어 모두 1로 설정하는 것과 같습니다.
입력
Bulbs[]= { 1,0,1,0 } 출력
Minimum right flips: 3
설명
원래 상태 1010
Press switch 2:- 1:101 flip count=1 Press switch 3:- 11:10 flip count=2 Press switch 4:- 111:1 flip count=3
입력
Bulbs[]= { 1,0,0,0 } 출력
Minimum right flips: 1
설명
Original state 1000 Press switch 2:- 1:111 flip count=1
오른쪽 전구가 모두 켜져 있습니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수는 N개의 전구 상태를 저장합니다.
-
함수 minFlips(int arr[],int n)는 배열과 그 길이 n을 입력으로 사용하고 배열의 설정 값에 대한 오른쪽 뒤집기의 최소 횟수를 반환합니다(모든 전구 끄기)
-
가변 개수는 뒤집기 횟수를 저장하는 데 사용되며 처음에는 0입니다.
-
Array switch[]는 i번째 전구에 해당하는 모든 스위치의 초기 상태를 저장하는 데 사용됩니다. 모두 0입니다( switch[]={0}.)
-
i=0에서 n까지 다음을 수행합니다. -
-
전구가 켜져 있고 스위치가 꺼져 있으면 아무 것도 하지 않음(i 증가)
-
전구가 꺼져 있고 스위치가 켜져 있으면 스위치를 끄면 전구 상태에 아무 것도 하지 않으므로 아무 것도 하지 않습니다(i 증가).
-
전구가 꺼져 있고 스위치가 꺼져 있으면 오른쪽에 있는 모든 전구의 개수와 회전 상태를 늘립니다. ( while 루프 )
-
-
for 루프가 끝나면 'count'에 있는 결과를 뒤집기 완료로 반환합니다.
- 반환 횟수.
예시
// C++ program to find minimum number of move-to-front
// moves to arrange items in sorted order.
#include <bits/stdc++.h>
using namespace std;
// Calculate minimum number of moves to arrange array
// in increasing order.
int minFlips(int arr[], int n){
int count = 0;
int swich[n] = {0}; //Initially we don't flip the states, so flip is false
for(int i=0;i<n;i++){
if(arr[i]==1 && swich[i]==0)
i++;
if(arr[i]==0 && swich[i]==1)
i++;
if(arr[i]==0 && swich[i]==0){
count++;
int j=i;
while(j<n){
if(arr[j]==0)
arr[j++]=1;
else
arr[j++]=0;
}
}
}
return count;
}
int main(){
int Arr[] = {0,1,0,1};
int N = 4;
cout <<”Minimum right flips to set all values in an array:"<<
minFlips(Arr, N);
return 0;
} 출력
Minimum right flips to set all values in an array: 4