문제 이해 단계
빨간색 : 누르는 버튼과 대응되는 스위치
파란색 : 버튼에 영향을 받는 스위치
문제는 N개의 스위치와 버튼이 나열되어 있는데 각각 1대 1 대응된다.
I번 버튼을 누르면, 그 버튼 번호의 스위치와 양옆에 있는 스위치가 반전된다.
초기 상태와 결과 상태가 주어질 때
초기 상태에서 결과 상태까지 만드는 최수를 구하는 문제이다.
문제 접근 단계
일단 대략적으로 문제의 유형부터 생각해 보기로 했다.
DP?
처음에는 Dp로 풀까 생각했었는데,
1. 처음 시작하는 수가 고정되어 있지 않다.
2. n = 1 일 때 3, n = 2 일 때 4.. 뭐 이런 식으로 값이 고정된 것도 아니다.
위의 근거로, dp는 아닌 것 같았다.
Greedy?
그리디로 생각한 이유는 간단하다.
그냥 문제에서 "최소를 구해라"라고 했기 때문이다.
최소를 구하라는 말은 그리디에서 많이 쓰는 말이어서 그냥 그리디인가?
라고 생각하고 일단 시작했다.
일단 전혀 느낌이 오지 않기 때문에 다양한 테스트 케이스를 해본다.
여러 가지를 끄적이다 보니 드는 의문이
'버튼을 누르는 순서가 결과의 영향을 끼칠까?'이다.
그래서 위의 예제 케이스로 한번 해봤다.
첫 번째는 1 -> 2 -> 3 순서
두 번째는 2 -> 3 -> 1 순서
마지막 결과는 동일하게 010이 나오는 것을 확인할 수 있다.
즉, 버튼을 누르는 순서는 상관없다.
이 말을 다르게 해석하면 선택 순서가 상관없기 때문에
처음부터 순차적으로 비교해도 상관없다.
이제 이 문제에 대해서 두 가지를 알고 있다.
1. 최소한의 개수를 구하는 문제
2. 순차적으로 탐색 가능
나는 맨 처음 이 문제를 그리디라고 가정했는데,
그리디는 미래를 생각하지 않고 각 단계에서 최선의 선택을 하는 것이기 때문에
그리디는 위 조건에 부합하다.
그래서 이 문제는 그리디로 충분히 풀어볼 만해서
그대로 그리디로 풀어보기로 했다.
순차적으로, 스위치 하나하나의 관점에서,
처음의 상태에서 끝의 상태로 갈 때를 따져보자.
만약 000 -> 110이 될 때,
첫 번째 자리에 있는 0이 1이 될 때를 따져보자는 것이다.
초록색 : 현재 비교하교 있는 스위치
1번 버튼부터 순차적으로 살펴보자.
먼저 1번 스위치는 1 -> 0 이므로 반전돼야 한다.
가능한 경우의 수는 2가지로 나뉜다.
각 버튼이 눌려 반전이 된 상태이다.
1번 스위치에서 누를 수 있는 버튼이 최대 2개인 이유는,
1번 스위치가 0 -> 1로 바뀌기 위해 영향을 줄 수 있는 버튼이
1번, 2번 버튼 총 2개밖에 없기 때문이다.
순차적으로 살펴보기로 했으니 이제 2번 스위치로 넘어가자.
2번 스위치로 넘어와서 생각해 보자.
2번 스위치에서 누를 수 있는 버튼은 총 1,2,3번 총 3개일까?
그렇지 않다. 왜냐하면 앞에처럼 2번을 누를 때를 생각해 보자.
위에서 애써 1번 스위치를 0으로 바꿔놨는데 다시 1로 바뀌었다.
이를 다시 0으로 바꾸기 위해 추가적으로 버튼을 누르는 동작이 필요하다.
이는 우리가 구해야 하는 최소 횟수가 아니다.
즉, 2번 스위치에 누를 수 있는 것은
1번 스위치에는 영향을 주지 않고 2번 스위치에는
영향을 줄 수 있는 3번 버튼밖에 없는 것이다.
3번 스위치로 넘어가 보자.
주황색 : 이미 탐색을 마친 스위치
이것도 2번 스위치와 마찬가지인 원리로 4번 버튼밖에 누르지 못한다.
그래서 4번 버튼을 누르고 이 상태를 갱신해 준다.
마지막 4번 스위치에서 1,2,3번 스위치에 영향을 주지 않는 버튼이 있는가?
존재하지 않는다.
즉, 4번 스위치에서 누를 버튼은 존재하지 않기 때문에
4번 스위치에서는 아무런 버튼을 누르지 않는다.
이제 모든 스위치를 탐색했으므로 결과 스위치와 현재 상태 스위치를 비교해 본다.
그런데 서로 상태가 다르다. 그래서 이건 틀렸다.
그렇다면 이 방식은 틀린 건가?
그렇지 않다. 아직 모른다.
왜냐하면 이건 1번 스위치에서 나뉜 2가지 케이스 중 하나이기 때문이다.
그럼 두 번째 케이스를 한번 똑같은 연산 과정을 거쳐보겠다.
이 케이스에서는 두 번째 스위치에서 결과 상태와 같아진다.
그래서 2회라는 결과를 얻을 수 있었다.
이 로직이 틀리지 않았다는 것을 알았다.
이제 이를 일반화해 보겠다.
1번부터 N번 스위치까지 탐색한다고 하면 이렇게 된다.
2 ~ (N-1) 번 스위치 : (자기 번호 + 1) 번 버튼 누름
N번(마지막) 스위치 : 아무 버튼도 안 누름
위 로직의 공통점은 경우의 수가 갈리지 않고 고정되어 있다는 것이다.
즉 방식이 1가지란 소리다.
경우의 수가 갈리는 것은 1번 스위치 하나밖에 없다.
이 말을 다르게 하면 최소 횟수를 결정하는 것은 1번 스위치이다.
1번 스위치에서 나올 수 있는 경우의 수는
1. 두 수가 같은 경우
2. 두 수가 다른 경우가 두 가지이다.
같은 경우는 또 이렇게 두 가지로 나뉜다.
다른 경우 또한 버튼 누르는 방식이 두 가지로 나뉜다.
이제 이를 통해 대략적으로 알고리즘을 구성해 보자.
1. 초기 스위치와 결과 스위치를 1번부터 순차적으로 비교
2. 1번 스위치에서 경우의 수를 2가지로 나눔
3. (2 ~ N-1) 스위치까지 초기와 결과 스위치 비교
-> 다를 경우 i+1번째 버튼 누르고 count+1
4. N번 스위치까지 오면 현재 스위치와 결과 스위치 비교, 같으면 count 반환
문제 구현 단계
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define MAX 1000000
int N;
string startStr,endStr;
int Solution(){
int val = MAX;
if(startStr == endStr) return 0;
if(startStr[0] == endStr[0]){
val = min(Cal(true,0),Cal(true,2));
}
else val= min(Cal(false,1),Cal(false,3));
return val;
}초기상태를 입력받을 startStr과 결과상태를 입력받을 endStr이다.
MAX는 나중에 최솟값을 구해주기 위해서 혹시 모를 오류를 방지해 주기 위함이다.
Solution() 함수를 설명하면 일단 두 상태가 처음부터 같다면
함수를 돌릴 필요가 없기 때문에 바로 0을 반환한다.
그리고 가장 중요한 1번째 스위치를 비교한다.
핵심 연산을 하는 Cal로 넘어가 둘 중 작은 값을 반환한다.
int Cal(bool same, int check){
int count = 0;
vector<int> cnt;
vector<int> fin;
for(int i = 0; i < startStr.length(); i++) {
cnt.push_back(startStr[i]-'0');
fin.push_back(endStr[i]-'0');
}
if(same){
count = check;
cnt[2] = (check == 2)? ((cnt[2] == 1)? 0 : 1) : cnt[2];
}
else{
count = 1;
cnt[0] = (cnt[0] == 1) ? 0 : 1;
cnt[1] = (cnt[1] == 1) ? 0 : 1;
if(check == 3) cnt[2] = (cnt[2] == 1) ? 0 : 1;
}
for(int i = 1; i < cnt.size(); i++){
if(cnt[i] != fin[i] && i+1 < N) {
count++;
for(int j = 0; j <=2; j++)
if(i+j < N) cnt[i+j]= (cnt[i+j] == 1) ? 0 : 1;
}
}
for(int i = 1; i < cnt.size(); i++) if(cnt[i] != fin[i]) return MAX;
return count;
}전구가 결과상태와 같아질 수 있는지
그리고 횟수를 세어주는 핵심 함수인 Cal이다.
매개변수로 1번 스위치가 같은지에 대한 참 거짓 유무,
두 번째로는 각각의 케이스를 구분하기 위한 것이다.
2 : 1번, 2번 버튼을 둘 다 누르는 경우
0 : 1번 2번 버튼을 둘 다 누르지 않는 경우
3 : 1번 버튼 o 2번 버튼 x
1 : 1번 버튼 x 2번 버튼 o
일단 string 값을 int로 변환해 vector에 담는다.
만약 same == true의 계산이라면 count == check로 미리 잡아두고 현재 상태를 거기에 맞춰 변환시킨다.
same == false라면 count = 1로 잡아두고 현재 상태를 갱신한다.
그 이후의 연산은 동일하므로 같은 반복문을 실행한다.
해당 자리의 값이 다르면 i, i+1, i+2까지 반전시킨다.
이 반복이 끝나면 모든 벡터가 다 같은지 확인하고
같으면 count를 반환하고 다르면 MAX를 반환한다.
MAX를 반환하는 이유는 반환 이후 비교에서 검출되지 않게 하기 위함이다.
핵심 코드는 여기서 설명이 끝이고 아래에서 전체코드를 올리고 설명을 마치겠다.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define MAX 1000000
int N;
string startStr,endStr;
int Cal(bool same, int check){
int count = 0;
vector<int> cnt;
vector<int> fin;
for(int i = 0; i < startStr.length(); i++) {
cnt.push_back(startStr[i]-'0');
fin.push_back(endStr[i]-'0');
}
if(same){
count = check;
cnt[2] = (check == 2)? ((cnt[2] == 1)? 0 : 1) : cnt[2];
}
else{
count = 1;
cnt[0] = (cnt[0] == 1) ? 0 : 1;
cnt[1] = (cnt[1] == 1) ? 0 : 1;
if(check == 3) cnt[2] = (cnt[2] == 1) ? 0 : 1;
}
for(int i = 1; i < cnt.size(); i++){
if(cnt[i] != fin[i] && i+1 < N) {
count++;
for(int j = 0; j <=2; j++)
if(i+j < N) cnt[i+j]= (cnt[i+j] == 1) ? 0 : 1;
}
}
for(int i = 1; i < cnt.size(); i++) if(cnt[i] != fin[i]) return MAX;
return count;
}
int Solution(){
int val = MAX;
if(startStr == endStr) return 0;
if(startStr[0] == endStr[0]){
val = min(Cal(true,0),Cal(true,2));
}
else val= min(Cal(false,1),Cal(false,3));
return val;
}
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin >> N;
cin >> startStr >> endStr;
int val = Solution();
int ans = (val >= MAX) ? -1 : val;
cout << ans;
}마지막 ans의 삼항연산자는 값이 MAX라는 뜻은 정답이 없다는 뜻이므로 -1을 출력한다.
시행착오
처음에는 DP로 푸는 문제인 줄 알고 DP로 접근하다가 완전히 틀려먹었다.
확실히 문제 유형을 알고 푸는 것과 유형을 모르고 푸는 것은 엄청난 차이가 있는 것 같다.
그리디인 것을 알아차렸어도, 로직을 알아도 구현하는데 꽤나 애먹었다.
구현도 어렵고 생각해 내기도 정말 어려웠던 문제 같다.
아니면 그리디를 오랜만에 풀어서일지도 모르겠다.