35154번 - ProblemSolving이 아니에요 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 203 | 86 | 70 | 45.752% |
문제
지훈이는 PS라는 자료구조를 만들었다. 하지만 PS라는 이름의 특성상 ProblemSolving으로 오해받고는 한다.
PS 자료구조는 문자 P를 저장하는 스택(Stack)으로, 다음 두 명령어를 사용한다.
PP: 문자P하나를 PS 스택 맨 위에 push한다.P: PS 스택 맨 위의 문자P하나를 pop한다. 단, PS 스택이 비어 있을 때는 수행할 수 없다.
지훈이는 명령어들을 공백 없이 이어 붙이면 P의 나열이 된다는 사실을 알았다. 문득, P가 $N$개 나열된 문자열이 주어졌을 때 이를 유효한 명령어로 해석하는 방법이 총 몇 가지나 될지 궁금해졌다.
처음에 PS 스택이 비어 있을 때, $N$개의 P로 이루어진 문자열을 유효하게 해석할 수 있는 경우의 수를 구해보자. 비어 있는 PS 스택에서 pop을 하는 경우 유효하지 않은 해석임을 유의하자.
입력
첫 번째 줄에 테스트 케이스의 개수 $T(1\le T\le 5\, 000)$가 주어진다.
두 번째 줄에 각 테스트 케이스의 $N$을 의미하는 서로 다른 정수 $N_1,N_2,\cdots ,N_T(1\le N_i\le 5\, 000)$가 공백으로 구분되어 오름차순으로 주어진다.
출력
첫 번째 줄부터 $T$줄에 걸쳐 각 테스트 케이스 별로 한 줄씩 정답을 $998\, 244\, 353$으로 나눈 나머지를 출력한다. 단, 유효하게 해석할 수 있는 방법이 없다면 대신 -1을 출력한다.
예제 입력 1
3 5 7 10
예제 출력 1
2 3 10
$5$개의 P로 이루어진 문자는 아래 $2$가지 방법으로 해석할 수 있다.
PP/PP/PPP/P/PP
$7$개의 P로 이루어진 문자는 아래 $3$가지 방법으로 해석할 수 있다.
PP/PP/PP/PPP/PP/P/PPPP/P/PP/PP
$10$개의 P로 이루어진 문자는 아래 $10$가지 방법으로 해석할 수 있다.
PP/PP/PP/PP/PPPP/P/PP/P/PP/PPPP/P/PP/PP/P/PPPP/P/PP/PP/PP/PPP/PP/P/P/PP/PPPP/PP/P/PP/P/PPPP/PP/P/PP/PP/PPP/PP/PP/P/P/PPPP/PP/PP/P/PP/PPP/PP/PP/PP/P/P
예제 입력 2
2 4999 5000
예제 출��� 2
609226471 509890175
출처
University > 고려대학교 > 고려대학교 프로그래밍 경시대회 > 2025 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 2 E번
- 문제를 만든 사람: leeminjae
- 문제를 번역한 사람: foxpython
- 문제를 검수한 사람: austin0817, cywohoy, dong0625, ezh8n, foxpython, kidw0124, mathjuny, sksms1375, sshs29hanul, tlsdydaud1, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호