31073번 - 카탈란 게임 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 417 | 96 | 89 | 29.966% |
문제
괄호 문자열은 여는 괄호 (와 닫는 괄호 )로만 이루어진 문자열을 의미한다. 올바른 괄호 문자열은 다음과 같이 정의된다.
- 빈 문자열은 올바른 괄호 문자열이다.
S가 올바른 괄호 문자열이라면,(S)도 올바른 괄호 문자열이다.S와T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 괄호 문자열ST도 올바른 괄호 문자열이다.
위 과정을 통해 만들어질 수 없는 모든 괄호 문자열은 올바른 괄호 문자열이 아니다.
최근 준희는 길이가 $2n$인 올바른 괄호 문자열의 개수가 카탈란 수 ${C}_{n}$개라는 사실을 알게 되었다. 올바른 괄호 문자열을 좋아하는 준희는 올바른 괄호 문자열이 전체 괄호 문자열 중 너무 낮은 빈도로 등장한다고 생각하여 슬퍼하고 있었다.
지민이는 준희를 위로해 주기 위하여, 올바른 괄호 문자열이 충분히 많이 존재한다는 것을 보여주기로 하였다. 지민이는 다음과 같은 게임에서 준희에게 승리하여 올바른 괄호 문자열이 충분히 많다는 것을 보여주고 싶다.
길이 $N$인 올바르지 않은 괄호 문자열 $S$에서, 두 명이 번갈아 가며 지울 문자가 없어질 때까지 맨 앞의 문자 또는 맨 뒤의 문자를 지운다. 게임 중 $S$가 빈 문자열이 아닌 올바른 괄호 문자열이 되는 순간이 존재한다면 지민이가 승리한다. 게임이 끝날 때까지 빈 문자열이 아닌 올바른 괄호 문자열이 등장하지 않으면 준희가 승리한다.
게임은 지민이가 먼저 시작한다. 길이 $N$과 문자열 $S$가 주어졌을 때, 지민과 준희가 모두 최적의 선택만을 내린다면 누가 게임에서 이길지 알아보자.
입력
첫째 줄에는 괄호 문자열의 길이 $N$이 주어진다.
둘째 줄에는 괄호 문자열 $S$가 주어진다.
출력
지민이와 준희 모두 최선을 다해 게임을 했을 때, 승리하는 사람을 출력한다.
지민이가 게임에서 승리한다면 jimin을, 준희가 승리한다면 junhui를 출력한다.
제한
- $1\leq N\leq 5\times{10}^{5}$
- $\left| S \right| =N$
- $S$의 모든 문자는
(또는)이다. - $S$는 올바른 괄호 문자열이 아니다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 8 | $N \le 20$ |
| 2 | 30 | $N \le 1000$ |
| 3 | 62 | 추가 제한 조건이 없다. |
예제 입력 1
4 ())(
예제 출력 1
junhui
예제 입력 2
7 (()()((
예제 출력 2
jimin
출처
School > 서울과학고등학교 > SciOI 2023 C-1번
- 문제를 만든 사람: sos89756
- 문제를 검수한 사람: mjhmjh1104, naeby, nick832, physics07, utilforever, whqkrkt04
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호