백준 30521번: Mike Sees The Storm (Large)
https://www.acmicpc.net/problem/30521 30521번: Mike Sees The Storm (Large) $N=2$, $K=2$일 때 Mike가 얻을 수 있는 수열의 목록은 [$-1, -2, -1, 0$], [$-1, 0, -1, 0$], [$-1, 0, 1, 0$], [$1, 2, 1, 0$], [$1, 0, 1, 0$], [$1, 0, -1, 0$] 총 $6$가지로, 최댓값의 $K$제곱을 합하면 $7$이다. www.acmicpc.net 카탈란 수의 응용입니다. 먼저 주어진 문제를 격자 속의 최단 경로 문제로 환원합니다. 칠판에 적힌 숫자를 $a$에서 $a-1$ 로 바꾸는 연산을 오른쪽으로 한 칸 이동하는 것으로, $a$에서 $a+1$로 바꾸는 연산을 위로 한 칸 이동하는 것..
백준 30169번: Primes and Multiplication
https://www.acmicpc.net/problem/30169 30169번: Primes and Multiplication In the first example, $f(10, 1) = g(1, 2) \cdot g(1, 5) = 1$, $f(10, 2) = g(2, 2) \cdot g(2, 5) = 2$. In the second example, actual value of formula is approximately $1.597 \cdot 10^{171}$. Make sure you print the answer modulo $(10^{9} + 7)$. In the third www.acmicpc.net 문제에서 나오는 $f(x,y)$와 $g(y,p)$의 정의를 잘 관찰해보면, $$ \prod_{i..
백준 27318번: 세상에서 가장 달달한 디저트 만들기 (integer)
https://www.acmicpc.net/problem/27318 27318번: 세상에서 가장 달달한 디저트 만들기 한별이는 튀르키예와 그리스의 전통 젤리인 로쿰을 만들고 있다. 로쿰은 녹말, 물, 설탕, 레몬즙 등을 냄비에 넣고 끓여서 걸쭉해질 때까지 저어준 다음, 겉에 슈가파우더를 뿌려서 굳히는 디저 www.acmicpc.net 행렬 거듭제곱이 더 떠올리기 쉬운 풀이같긴 한데, 일반항을 구해서 풀 수 있는 문제이므로 일반항을 구하는 방법도 소개합니다. 이 글에서 $$V(N,M) = (12N-16)^{M}$$ 이고 $$S(N,M) = (4N-4) \times S(N,M-1) + (24N-48) \times V(N,M-1)$$ 이라는 걸 이미 설명했으니, 해당 지점부터 이어가겠습니다. 덧붙여, $$V(..