문제 출처가 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) 이다.