문제 링크 (2026/4/7 기준) Gold I 문제 읽기 알파벳 대문자로만 이루어진 문자열 $S$가 주어집니다. $S$를 최소 개수의 팰린드롬을 분할할 때, 최소 분할 개수를 구해봅시다. 풀이 $|S|$가 최대 $2,500$으로, 생각보다 작습니다. $\mathcal{O}(|S|^2)$풀이를 생각해봅시다. 먼저, 팰린드롬 문자열이 애초에 어떻게 이루어지는지 고민해봅시다. $\Sigma = \lbrace \texttt{A}, \texttt{B}, \cdots, \texttt{Z} \rbrace$에 대해, $$ T \rightarrow \varepsilon \mid a \mid aTa \quad (a \in \Sigma) $$ 로 정의할 수 있습니다. 뭔 소리냐? 팰린드롬은 길이가 $0$ 또는 $1$인 문자열의 양 끝에 같은 문자를 하나씩 $0$회 이상 재귀적으로 붙인 꼴이라는 것입니다....
문제 링크 (2024/9/13 기준) Gold V 문제 읽기 문제가 살짝 난해합니다; $1$초부터 $T$초까지 매 초 $1$번 나무 또는 $2$번 나무에서 하나씩, 총 $T$개의 자두가 떨어집니다. $W$번 이하로 이동하며 떨어지는 자두를 받았을 때의 최댓값을 구해봅시다. 처음 시작은 $1$번 나무입니다. 풀이 제한을 잘 살펴봅시다. $T \leq 1 000$, $W \leq 30$, 나무가 $2$그루 있으니, dp[현재 시간][현재 위치][현재까지 이동한 횟수]로 3차원 DP를 해볼 수 있을 것 같습니다. 우선, DP 테이블에 초깃값들을 채워봅시다. $t$초에 자두가 떨어진 나무의 위치를 $P_t$라고 하면, $1$초에 $1$번 나무에서 시작하니, $DP_{1, 1, 0}=[P_i = 1]$이 되겠고 (편의상 $[c]$는 조건 $c$가 참이면 $1$, 거짓이면 $0$ 값을 가진다고 약속합시다), $1$초에 자두가 떨어지기 전 $2$번 나무로 움직였다면, $DP_{1, 2, 1}=[P_i = 2]$가 됩니다....