돌 뒤집기 게임
면접 대비시간 제한1초메모리 제한1024 MB
H/T 돌이 일렬로 놓여 있을 때, 앞면 돌을 하나 뒤집고 이웃 중 앞면이 정확히 2개면 같은 사람이 계속하는 게임에서 누가 이기는지 판정한다.
문제
철수와 영희는 돌 뒤집기 게임을 하려고 한다.
돌 뒤집기 게임은 앞면과 뒷면을 구분할 수 있는 개의 돌을 사용한다. 게임을 시작하기 전 심판은 개의 돌을 일렬로 배치한다. 이때 에 대해 번째 돌과 번째 돌은 서로 인접해 있다. 각 돌은 앞면 또는 뒷면이 보이도록 놓여 있으며, 초기에 최소 개 이상의 돌은 앞면이 보이도록 배치되어 있다. 게임은 철수부터 시작해서 아래의 과정을 수행하며 턴을 진행한다.
- 앞면이 보이는 돌 하나를 고른다. 만약 앞면이 보이는 돌이 없다면 패배한다.
- 번 과정에서 고른 돌을 뒤집어서 뒷면이 보이도록 바꾼다.
- 뒤집은 돌의 인접한 돌 중 앞면이 보이는 돌이 개라면 번 과정으로 돌아간다. 그렇지 않다면 상대에게 차례를 넘긴다.
두 사람은 이 게임의 필승법을 알고 있으며, 이를 활용하여 자신의 턴을 진행한다. 게임을 시작하기 전 돌의 초기 상태가 입력으로 주어졌을 때 누가 승리하는지 판단해 보자.
입력
첫 줄에 돌의 개수 이 주어진다. ()
둘째 줄에 길이 의 문자열이 주어진다. 번째 문자는 번째 돌의 초기 상태를 의미하며, H면 앞면, T면 뒷면이 보이고 있음을 의미한다.
출력
철수가 이긴다면 First, 영희가 이긴다면 Second를 출력한다.