백준 32864번 지나칠 수 없는 지하철 게임 [C++]

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

 

 

#문제 간단 정리

분류는 애드혹 + 게임이론으로 되어있는데...

 

대충 그리디하게 생각해서 풀었다고 생각한다.

 

 

#문제 해결 방법

 

두명다 최선의 방법을 사용하기 때문에

 

만약 종착역에 도착하기전에 1 (환승역이 있다면) 그 이후에 

0(일반역) 에서 멈춰서 승리하려고 하기 때문에

 

나는 뒤에서부터 역산해서 누가 이기면 되는지 추정하면 된다고 생각해서

 

뒤에부터 만약 1이 온다면 1뒤에 0이오면 승리자가 그대로고 (01)

1뒤에 1이 오게 되더라도 바로 자기턴이 돌아오기때문에 상관없다 (11)

 

다만 2번째역이 환승역이라면 (index 1)  

 바로 환승을해야 되기 때문에 

기존의 승리자가 바뀌게 된다

 

뭐 대충 이렇게 시뮬레이션해서 풀었다.

 

#전체 코드

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int n;

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

    cin >> n;
    vector<int> lines(n);
    
    for (int i = 0; i < n; i++) {
        cin >> lines[i];
    }

    int whoWin = 0; //0 세훈 1 민아
    for (int i = n - 2; i >= 0; i--) {
        if (lines[i] == 0) {

        }
        else if(lines[i]== 1) {

            if (i == 1) {
                if (whoWin == 1) whoWin = 0;
                else whoWin = 1;
                i--;
            }
            else if (lines[i - 1] == 0) {
                if (whoWin == 1) whoWin = 1;
                else whoWin = 0;
                i--;
            }
            else if (lines[i - 1] == 1) {
                if (whoWin == 1) whoWin = 1;
                else whoWin = 0;
                i--;
            }
        }
    }

    if (whoWin==0) {
        cout << "mnx" << '\n';
    }
    else {
        cout << "alsdkffhgk" << '\n';
    }

    return 0;
}