https://www.acmicpc.net/problem/2138
문제
N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.
N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.
출력
첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.
코드
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
int N;
vector<int> light;
vector<int> light2;
vector<int> temp;
int ans = 0;
bool checkAns(){
for(int i=0; i<N; ++i){
if(light[i] != light2[i]){
return false;
}
}
return true;
}
int turn(int a){
if(a == 0){
return 1;
}
else{
return 0;
}
}
int main(void){
cin >> N;
for(int i=0; i<N; ++i){
int a;
scanf("%1d", &a);
light.push_back(a);
}
for(int i=0; i<N; ++i){
int a;
scanf("%1d",&a);
light2.push_back(a);
}
temp = light;
for(int i=1; i<N; ++i){
// i-1번째 전구를 확인
if(light[i-1] != light2[i-1]){
ans++;
light[i-1] = turn(light[i-1]);
light[i] = turn(light[i]);
if(i != N-1){
light[i+1] = turn(light[i+1]);
}
}
}
if(checkAns()){
cout << ans;
return 0;
}
먼저 N이 10^5이기 때문에 이중 반복문을 쓰면 시간 초과가 난다 때문에 O(nlogn)이나 O(n)의 해결 방법을 찾아야 하는데
이때 생각 할 수 있는게 그리디 방법이다.
이 문제에 그리디를 어떻게 적용할까 잘 생각해보면 전구의 순서대로 불을 조정하는 것이다.
무슨 뜻이냐 하면은 만약 첫번째나 마지막 전구 이외의 다른 전구 번호의 버튼을 누르면 i-1, i, i+1번의 전구들의 불이 바뀌게 된다.
이때, i-1번의 전구만 생각하면 된다.
i-1번의 전구에 영향을 끼치는 건 i-2번 버튼, i-1번 버튼, i번 버튼이다. i+1번의 버튼은 i-1번 전구에 영향을 줄 수 없기 때문에 무조건 i번 버튼에서 i-1번의 전구 불이 알맞게 들어야 한다.
이를 좀 더 생각해보면 첫 번째 전구에 힌트가 있다.
첫번째 전구에 영향을 주는 버튼은 첫번째 전구와 두번째 전구가 있다.
즉, 첫번째 전구를 키는 경우와 키지 않는 경우를 나눌 수 있다.
이 두경우를 나눠 불을 켜보고 만약 그럼에도 답과 맞지 않는다면 -1을 출력한다.
'PS > Greedy' 카테고리의 다른 글
[1744] 수 묶기 (0) | 2023.07.18 |
---|---|
[1931] 회의실 배정 (0) | 2023.05.02 |
[11047] 동전 0 (0) | 2023.05.02 |