====== Tea time in the grand garden ======

===== 풀이 =====
  * 문제 출처가 JAG Summer Camp 2023 Day2 와 Petrozavodsk Programming Camp 2024 Summer Day 1 인데, 동일한 문제인데 문제 이름이 다르게 되어있다.
    * Petrozavodsk camp 의 [[https://qoj.ac/download.php?type=attachments&id=1751&r=1|에디토리얼]]에서는 문제제목이 Fruit Tea 로 되어있다
  * 문제를 대충 정리하면, 온도가 증가할때의 증가량들을 다 더한 값이 K가 되면 된다. 온도는 0에서 출발해서 0에서 끝나고, 0미만으로 떨어지면 안된다고 했으니, 이것을 바꿔쓰면 [[ps:tutorial:올바른 괄호 문자열]]과 비슷한 형태로 바꿀수 있다. K개의 '('와 K개의 ')'가 있는 괄호 문자열을 N+1개의 부분문자열 (빈 문자열도 가능)로 분할하는 것과 동일한 문제가 된다. 이때, 각 부분문자열은 '(' 와 ')'중 한 종류로만 이루어져야 한다는 조건이 붙는다
  * 조건이 없으면 길이 2K의 괄호문자열에 N개의 구분자를 추가하는 방법의 수를 세는 기초적인 조합 문제가 된다.
  * 조건을 고려할 경우에는, 주어진 괄호문자열에서 '()' 또는 ')(' 사이에 반드시 구분자를 포함시킨 뒤에 하고, 남은 구분자들을 넣는 방법의 수를 세는 문제가 된다. 
  * '()' 의 개수를 x개로 고정시킨다면, ')('의 개수는 항상 x-1개이므로, 총 2x-1 개의 구분자의 위치가 고정된다. 그러면 N-(2x-1)개의 구분자를 자유롭게 넣는 방법의 수는 C(2K+N-(2x-1), N-(2x-1))개 이다. 한편 길이 2K의 올바른 괄호문자열 중에서 '()' 의 개수가 x인 문자열의 개수는 [[ps:tutorial:나라야나 수]] 로 계산할 수 있다. 팩토리얼 모듈로 값들을 모두 전처리해두면, 이 값은 O(1)에 구할수 있다.
  * 이제 모든 x에 대해서 위 값들을 모두 구해 더하면 답을 구할수 있다. 전처리를 포함한 총 시간복잡도는 O(N+K) 이다.

===== 코드 =====
  * 다이아몬드 이상은 코드 생략

{{tag>BOJ ps:problems:boj:다이아몬드_3}}