백준 20173번 Imprecise Computer

 

acm-icpc 2020 서울 리저널에서 E번으로 출제되었던 문제이다. 

내 기억상으로 3번째로 많이 풀렸던 문제였는데.. 그때 우리는 풀지 못했었다 🥺

 

그것이 우리니까..

 

하지만 지금은 다르다!!

dp를 계속 풀다 생각나서 보니, 해답이 20분? 만에 떠올랐다. 디버깅 과정에서 많이 틀리긴 했는데,, 암튼 나 혼자 해결했다!

지금 생각해보니 그때 결과 보신 교수님은 우릴 어떻게 생각하셨을지... 😰 

 

문제 출처 : https://www.acmicpc.net/problem/20173

 

문제는 출처 참고하세요!

 

 

풀이

 

문제에서 컴퓨터가 잘못 판단할 경우는 수가 인접할 때 (1과 2, 2와 3 등) 밖에 없다.

따라서 모든 대결(?)을 볼 필요 없이 수가 다음과 같이 줄어들게 된다. 

(1, 2), (2, 3), (3, 4), ..., (n - 1, n)  

 

따라서 1과 n은 승수가 최대 1 차이나게 되고, 나머지 수는 2가 차이 날 수 있게 된다.

이렇게 보면 각 수당 경우의 수가 별로 없게 된다.

 

이제 각 수들의 입장에서 살펴보자.

 

어떤 수 i가 대결할 때는 총 2라운드에서 4가지 경우가 존재한다.

 

• 1라운드 승, 2라운드 승
• 1라운드 패, 2라운드 패
• 1라운드 승, 2라운드 패
• 1라운드 패, 2라운드 승

 

이때 어떤 수 i가 1과 n이 아니라면 1,2라운드 각각 2번씩 대결을 하게 되는데, 그 경우 4 x 4 = 16 가지 경우가 나온다.

하지만 이전 수 i-1에서 먼저 대결을 계산하고 결과를 넘겨준다면 i에서는 4가지 경우만 고려하면 된다.

(이 부분은 말이 좀 난해한데, 코드를 보면 이해가 쉬울 것이다.)

 

또한 어떤 수 i에 대한 대결을 확정 지었다면, 이 대결이 영향을 미치는 것은 오직 i+1의 대결이다.

반대로 i-1의 가능한 경우를 미리 조사했다면 i를 고려할 때 1 ~ i-2 에서의 대결 결과는 따로 볼 필요가 없다는 것이다.

 

따라서 dp[n][i][j] : 수 n이 (n, n+1)의 대결에서 1라운드에서 i번 승리했고, 2라운드에서 j번 승리할 수 있는가?로 생각해보자.

만약 (n-1, n) 의 대결에서 n이 1라운드 패, 2라운드 승이라 가정해보면

만약 v[n] = 2 라면 (n, n+1)의 대결에서 n이 1라운드 패, 2라운드 승을 가져와야 한다. (dp[n][0][1] = true)

반대로 n+1은 1라운드 승, 2라운드 패가 된다. (dp[n][1][0] = true)

 

이 결과를 다음 (n+1, n+2) 대결에서 넘겨주면 되는 것이다.

 

만약 이전 대결에서 1라운드 승, 2라운드 승인데, v[n] = 2 라면 이 때는 불가능하다. 한 번의 승부로 격차를 2승 이상 늘릴 수 없기 때문이다.

 

이 방법을 1 ~ n까지 하되, 1과 n은 따로 예외처리 과정이 필요하다.

배열의 크기가 최대 400만이며, dp 속성을 만족하기 때문에 메모이제이션 과정을 거치면 제한시간 내 해결 가능하다.

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

bool dp[1000010][2][2];
int n;
vector<int>v;

// 현재 idx 수는 기계 1에서 l번, 기계 2에서 r번 이긴 상태.
void go(int idx, int l, int r){
	bool& ret = dp[idx][l][r];
	if(ret != false) return;
	ret = true;
	
	if(idx > n) return;
	
	//두 기계의 승수가 같다.
	if(v[idx] == 0){
		//한번의 승부로 맞출 수 없음
		if(l == r) { //승승 or 패패인 경우
			go(idx + 1, 1, 1);
			go(idx + 1, 0, 0);
		}
		else{
			if(l > r) go(idx + 1, 1, 0); //r번 승리 -> 다음에겐 l번 승리
			else go(idx + 1, 0, 1);
		}
	}
	else if(v[idx] == 1){ //왼쪽 오른쪽 다른 경우
		if(abs(l - r) == 1) {
			go(idx + 1, 1, 1);
			go(idx + 1, 0, 0);
		}
		else if(l == r){ // 승승, 패패인 경우
			go(idx + 1, 1, 0);
			go(idx + 1, 0, 1);
		}
	}
	else{ //v[i] == 2
		if(l == r) return;
		else if(l > r) go(idx + 1, 0, 1); //l번 승리
		else go(idx + 1, 1, 0);
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	v.resize(n + 1);
	for(int i=1; i<=n; i++) cin>>v[i];
	
	for(int i=1; i<=n; i++){
		if((i == 1 && v[1] > 1) || (i == n && v[n] > 1) || v[i] > 2){
			cout<<"NO\n";
			return 0;
		}
	}
	
	if(v[1] == 0){
		go(2, 0, 0);
		go(2, 1, 1);
	}
	else if(v[1] == 1){
		go(2, 0, 1);
		go(2, 1, 0);
	}
	
	bool flag = false;
	for(int i=0; i<2; i++){
		for(int j=0; j<2; j++){
			if(v[n] == 0 && (i == j) && dp[n][i][j]) flag = true;
			if(v[n] == 1 && (i != j) && dp[n][i][j]) flag = true;
		}
	}
	
	if(flag) cout<<"YES\n";
	else cout<<"NO\n";
	return 0;
}