원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
가위바위보
원제: 가위바위보
문제
번부터 번까지 번호가 부여된 명의 사람이 일렬로 서 있다. ()번 사람은 왼쪽에서 번째에 서 있으며, 하나의 카드 를 가지고 있다. 각 카드는 가위(S), 바위(R), 보(P) 중 하나이다.
서로 다른 두 사람 사이에 다른 사람이 없다면, 그 두 사람은 서로 인접하다고 하자. 여러분은 인접한 두 사람을 골라 대결시킬 수 있다. 한 번의 대결은 다음과 같이 진행된다.
- 두 사람의 카드가 서로 다르면, 가위바위보 규칙에 따라 승자가 결정된다. 즉, 바위(
R)는 가위(S)를 이기고, 가위(S)는 보(P)를 이기고, 보(P)는 바위(R)를 이긴다. - 두 사람의 카드가 같으면, 여러분이 승자를 임의로 정할 수 있다.
- 패자는 퇴장하며, 승자는 자신의 카드를 그대로 유지한 채 그 자리에 남는다. 퇴장으로 인해 새롭게 인접해지는 두 사람이 생길 수 있으며, 두 사람은 이후 대결을 할 수 있다.
여러분은 정확히 번의 대결을 진행하여 단 한 명의 우승자만 남기려 한다. 각 사람에 대해, 그 사람이 우승자가 될 수 있도록 대결하는 방법이 존재하는지 판별하는 프로그램을 작성하라.
제약 조건
- 는 영어 알파벳 대문자
S,R,P로만 이루어진 길이 의 문자열이다.
부분문제
- (13점)
- (16점) 문자열 는 최대 두 종류의 문자로만 이루어져 있다.
- (47점)
- (31점)
- (43점) 추가 제약 조건 없음.
입력 형식
첫 줄에 정수 이 주어진다.
그다음 줄에 길이 의 문자열 가 주어진다. 의 번째 문자 는 번 사람이 가진 카드를 나타내며, 영어 알파벳 대문자 S, R, P 중 하나이다 ().
출력 형식
첫 줄에 길이 의 문자열을 출력한다. 이 중 번째 문자는, 번 사람이 우승자가 될 수 있다면 1, 아니면 0이어야 한다 ().
예제
예제 1
3 RPP
011
번과 번을 먼저 대결시키면 두 사람의 카드가 같으므로, 여러분이 임의로 승자를 정할 수 있다. 번을 승자로 정했다면, 남은 번과 번이 대결하면 보(P)가 바위(R)를 이기므로, 번이 우승자가 될 수 있다.
번과 번을 대결시켜 번을 승자로 정한 후, 번과 대결시키면, 번이 우승자가 될 수 있다.
바위(R)는 보(P)를 이길 수 없으므로, 번은 절대로 우승자가 될 수 없다.
예제 2
3 RPS
101
번과 번을 먼저 대결시키면 가위(S)가 보(P)를 이겨 번이 이긴다. 남은 번과 번이 대결하면 바위(R)가 가위(S)를 이기므로, 번이 우승자가 될 수 있다.
번과 번을 먼저 대결시키면 보(P)가 바위(R)를 이겨 번이 이긴다. 남은 번과 번이 대결하면 가위(S)가 보(P)를 이기므로, 번이 우승자가 될 수 있다.
번은 절대로 우승자가 될 수 없다.