돌 뒤집기 게임

면접 대비

시간 제한1초메모리 제한1024 MB

요약
H/T 돌이 일렬로 놓여 있을 때, 앞면 돌을 하나 뒤집고 이웃 중 앞면이 정확히 2개면 같은 사람이 계속하는 게임에서 누가 이기는지 판정한다.
난이도

보통10점 중 7점

유형
게임 이론, 조합론, 그리디
정답자
아직 제출이 없습니다

문제

철수와 영희는 돌 뒤집기 게임을 하려고 한다.

돌 뒤집기 게임은 앞면과 뒷면을 구분할 수 있는 NN개의 돌을 사용한다. 게임을 시작하기 전 심판은 NN개의 돌을 일렬로 배치한다. 이때 1≤i<N1 \leq i < N에 대해 ii번째 돌과 i+1i+1번째 돌은 서로 인접해 있다. 각 돌은 앞면 또는 뒷면이 보이도록 놓여 있으며, 초기에 최소 11개 이상의 돌은 앞면이 보이도록 배치되어 있다. 게임은 철수부터 시작해서 아래의 과정을 수행하며 턴을 진행한다.

  1. 앞면이 보이는 돌 하나를 고른다. 만약 앞면이 보이는 돌이 없다면 패배한다.
  2. 11번 과정에서 고른 돌을 뒤집어서 뒷면이 보이도록 바꾼다.
  3. 뒤집은 돌의 인접한 돌 중 앞면이 보이는 돌이 22개라면 11번 과정으로 돌아간다. 그렇지 않다면 상대에게 차례를 넘긴다.

두 사람은 이 게임의 필승법을 알고 있으며, 이를 활용하여 자신의 턴을 진행한다. 게임을 시작하기 전 돌의 초기 상태가 입력으로 주어졌을 때 누가 승리하는지 판단해 보자.

입력

첫 줄에 돌의 개수 NN이 주어진다. (1≤N≤1,000,0001 \leq N \leq 1\\,000\\,000)

둘째 줄에 길이 NN의 문자열이 주어진다. ii번째 문자는 ii번째 돌의 초기 상태를 의미하며, H면 앞면, T면 뒷면이 보이고 있음을 의미한다.

출력

철수가 이긴다면 First, 영희가 이긴다면 Second를 출력한다.

예제3

  1. 예제 1

    입력
    9
    HHHTHHHTH
    
    예상 출력
    First
    
  2. 예제 2

    입력
    10
    HHTHTTHHHH
    
    예상 출력
    Second
    
  3. 예제 3

    입력
    6
    HHHHHH
    
    예상 출력
    First