백준: 20173

</br> 2020 본선 중 골드 문제 풀기
</br>

20173: Imprecise Computer

https://www.acmicpc.net/problem/20173

이 컴퓨터는 2 차이 나는 애들은 대소 비교를 잘 하는데, 1 차이 애들은 이상하게 할 수도 있다
r(i)를 i가 크다고 판명난 횟수라고 하고, 두 번 시행해서, r1과 r2의 차 수열을 Pn이라 하면
Pn을 입력 받고 이게 이 컴퓨터가 계산한 결과일 수 있을까 확인하기

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int a, b;
    cin >> a;
    for(int i = 1; i < n; i++){
        cin >> b;
        if( a == 0 ){
            a = b;
            continue;
        }
        if( a == 1 ){
            a--;
            b--;
        }
        else{
            cout << "NO" << endl;
            return 0;
        }

        if( a != 0 ){
            cout << "NO" << endl;
            return 0;
        }
        a = abs(b);
    }
    if( a == 1 ) cout << "NO" << endl;
    else cout << "YES" << endl;

}

2 이상 차이 나는 애들끼리는 무조건 옳게 나오므로, 차를 구해도 다 0이 될 것이다.
따라서 i와 i+1 끼리 결과만 비교하면 되는데,

i  i+1     i  i+1
1  0       1  0
0  1       0  1
1  0       0  1
0  1       1  0

의 4가지 경우가 있을 것이다.
그럼 둘의 차를 구하면, 위의 (1,0)-(1,0)과 (0,1)-(0,1)은 같으므로 차가 (0,0)이고, 밑의 (1,0)-(0,1)과 (0,1)-(1,0)은 차가 (1,1)이 될 것이다.
아하~ 그럼 (0,0)과 (1,1) 중 하나를 선택할 수 있다고 생각해 주면 되겠다.

ex1) 백준 예제
5
1 0 2 0 1

i: 1 2 3 4 5
P: 1 0 2 0 1

i: 1 2
P: 1 0  에서 1번째가 1이므로 반드시 (1 1)이 되어야 함
(1 0)과 (1 1)의 차는 (0 1)이므로 P의 2번째를 1로 업데이트

i: 2 3
P: 1 2  에서 2번째가 1이므로 반드시 (1 1)이 되어야 함
(1 2)과 (1 1)의 차는 (0 1)이므로 P의 3번째를 1로 업데이트

i: 3 4
P: 1 0  에서 3번째가 1이므로 반드시 (1 1)이 되어야 함
(1 0)과 (1 1)의 차는 (0 1)이므로 P의 4번째를 1로 업데이트

i: 4 5
P: 1 1  에서 4번째가 1이므로 반드시 (1 1)이 되어야 함
(1 1)과 (1 1)의 차는 (0 0)이므로 P의 5번째를 0으로 업데이트

최종적으로 모두 0이 되었으므로 YES

ex2) 백준 예제
5
1 1 2 1 0

i: 1 2 3 4 5
P: 1 1 2 1 0

i: 1 1
P: 1 0  에서 1번째가 1이므로 반드시 (1 1)이 되어야 함
(1 1)과 (1 1)의 차는 (0 0)이므로 P의 2번째를 0으로 업데이트

i: 2 3
P: 0 2  에서 2번째가 0이므로 패스

i: 3 4
P: 2 0  에서 3번째가 2이므로 (1 1)이 되어도 (2 0)과 (1 1)의 차가 (1 1)이므로, 실패한다.

따라서 NO

</br>

---

다른 dp[][] 풀이도 있던데 그 쪽은 잘 모르겠다…

</br>