ps:problems:boj:30359
Tea time in the grand garden
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 30359 |
| 문제명 | Tea time in the grand garden |
| 레벨 | 다이아몬드 3 |
| 분류 |
조합론 |
| 시간복잡도 | O(n+k) |
| 인풋사이즈 | n<=2*10^5, k<=2*10^5 |
| 사용한 언어 | Python 3.13 |
| 제출기록 | 62764KB / 532ms |
| 최고기록 | 532ms |
| 해결날짜 | 2026/03/16 |
풀이
- 문제 출처가 JAG Summer Camp 2023 Day2 와 Petrozavodsk Programming Camp 2024 Summer Day 1 인데, 동일한 문제인데 문제 이름이 다르게 되어있다.
- Petrozavodsk camp 의 에디토리얼에서는 문제제목이 Fruit Tea 로 되어있다
- 문제를 대충 정리하면, 온도가 증가할때의 증가량들을 다 더한 값이 K가 되면 된다. 온도는 0에서 출발해서 0에서 끝나고, 0미만으로 떨어지면 안된다고 했으니, 이것을 바꿔쓰면 올바른 괄호 문자열 (Valid Parentheses)과 비슷한 형태로 바꿀수 있다. K개의 '('와 K개의 ')'가 있는 괄호 문자열을 N+1개의 부분문자열 (빈 문자열도 가능)로 분할하는 것과 동일한 문제가 된다. 이때, 각 부분문자열은 '(' 와 ')'중 한 종류로만 이루어져야 한다는 조건이 붙는다
- 조건이 없으면 길이 2K의 괄호문자열에 N개의 구분자를 추가하는 방법의 수를 세는 기초적인 조합 문제가 된다.
- 조건을 고려할 경우에는, 주어진 괄호문자열에서 '()' 또는 ')(' 사이에 반드시 구분자를 포함시킨 뒤에 하고, 남은 구분자들을 넣는 방법의 수를 세는 문제가 된다.
- '()' 의 개수를 x개로 고정시킨다면, ')('의 개수는 항상 x-1개이므로, 총 2x-1 개의 구분자의 위치가 고정된다. 그러면 N-(2x-1)개의 구분자를 자유롭게 넣는 방법의 수는 C(2K+N-(2x-1), N-(2x-1))개 이다. 한편 길이 2K의 올바른 괄호문자열 중에서 '()' 의 개수가 x인 문자열의 개수는 나라야나 수 (Narayana Number) 로 계산할 수 있다. 팩토리얼 모듈로 값들을 모두 전처리해두면, 이 값은 O(1)에 구할수 있다.
- 이제 모든 x에 대해서 위 값들을 모두 구해 더하면 답을 구할수 있다. 전처리를 포함한 총 시간복잡도는 O(N+K) 이다.
코드
- 다이아몬드 이상은 코드 생략
ps/problems/boj/30359.txt · 마지막으로 수정됨: 2026/03/16 08:50 저자 teferi
토론