본문 바로가기

분할 정복을 이용한 거듭제곱/행렬 거듭제곱

 (61)
백준 27318번: 세상에서 가장 달달한 디저트 만들기 (matrix) https://www.acmicpc.net/problem/27318 27318번: 세상에서 가장 달달한 디저트 만들기 한별이는 튀르키예와 그리스의 전통 젤리인 로쿰을 만들고 있다. 로쿰은 녹말, 물, 설탕, 레몬즙 등을 냄비에 넣고 끓여서 걸쭉해질 때까지 저어준 다음, 겉에 슈가파우더를 뿌려서 굳히는 디저 www.acmicpc.net 문제에서는 $N$과 $M$이 달라질 때마다 완전히 꽉 차있는 $\left ( N^{M} \right )^{3}$짜리 정육면체로부터 시작하지만, 어차피 최종 결과물은 $N,M$값에 상관없이 부피 1짜리 정육면체들로 이루어져있습니다. 즉, $N$을 고정시킨 뒤, $M$을 하나씩 늘리며 이전 단계의 로쿰이 몇 번 나타나는지 확인하는 게 떠올리기 쉬운 풀이 같습니다. 그림으로 주어..
백준 9819번: Color Change of Go Game Pieces https://www.acmicpc.net/problem/9819 9819번: Color Change of Go Game Pieces Assume that there are lots of two colors of black and white Go Game Pieces in a box, we take out n Go Game Pieces (0 < n < 129, n is a natural number) each time from the box, among which all the m pieces taken out earlier are white and the latter pieces ar www.acmicpc.net 단순히 문제를 그대로 시뮬레이션 하는 것으로 풀리는 문제이지만, $k$가 충분히 클 때 복..
백준 27435번: 파도반 수열 2 https://www.acmicpc.net/problem/27435 27435번: 파도반 수열 2 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ T ≤ 1,000, 1 ≤ N ≤ 1018) www.acmicpc.net 파도반 수열의 초반 항이 10개 주어져있고, 그림도 친절하게 주어져있어 점화식을 추론하기 쉽습니다. $$P(n) = P(n-1) + P(n-5)$$ 이 점화식에 따르면 $5 \times 5$ 행렬 거듭제곱을 통해 빠르게 답을 구할 수 있게 됩니다. $$ \begin{bmatrix} P(n+4) \\ P(n+3) \\ P(n+2) \\ P(n+1) \\ P(n) \end{bmatrix} = \begin{bmatrix} 1..
백준 17315번: Matrix Game (matrix interpretation) https://www.acmicpc.net/problem/17315 17315번: Matrix Game The input will contain the six integers n, m, a, b, c, and d. www.acmicpc.net National Olympiad in Informatics, China, 2013, Day2에 Problem1로 출제된 문제라고 합니다. 이 문제에 대해 행렬을 사용한 점화식, 일반적인 정수 계수 점화식 두 방법을 이용하여 풀었는데, 복잡도는 비슷하지만 상수 차이로 실행시간 차이가 컸습니다. 그리고 두 풀이가 꽤 상이한 듯하여 둘 다 소개하고자 합니다. 정수 거듭제곱 풀이에 대해 궁금하신 분은 이쪽 링크를 이용하시면 됩니다: Matrix Game (integer i..
백준 14553번: The Way https://www.acmicpc.net/problem/14553 14553번: The Way 여우와 토끼는 사이가 좋았다. 하지만 어느 날 토끼가 여우에게 갓겜 "히어로즈 오브 더 스톰"을 추천했고, 여우는 게임을 해보고 너무 화가나서 토끼를 쫓으러 갔다. 히어로즈 오브 더 스톰의 www.acmicpc.net 처음에 dp 식을 이상한 방향으로 접근해서 오랫동안 힘들었던 문제입니다. 우선 제가 AC 받은 접근은, $3 \times N$ 격자를 가장 왼쪽의 1열에서 2열로 넘어가는 모양새를 기준으로 subproblem을 나눕니다. 이게 무슨 뜻인지 경우의 수를 나누어 설명하겠습니다. 시작하는 칸에서 바로 오른쪽으로 이동 : 2열의 윗 칸에서 N열의 아랫 칸으로 가는 경우의 수 시작하는 칸에서 2열의 가운..
백준 13380번: Found https://www.acmicpc.net/problem/13380 13380번: Found Alice and Bob live in a city with N intersections (numbered as intersection 1, intersection 2,..., intersection N). There are M roads. Each road is bidirectional and directly joins two intersections. Each pair of intersections is joined by at most one road www.acmicpc.net 문제 지문을 읽어보면, $N$개의 intersection이 있고 $M$개의 road가 있고 $T$ 만큼 지난 후에 둘이 만납니다. ..
백준 24930번: Ordinary Ordinals https://www.acmicpc.net/problem/24930 24930번: Ordinary Ordinals Sets, sets, sets. Everything in math is just a set. Even the natural numbers can be represented as sets. For example, we can represent the the number $0$ as the empty set $\{\}$. The number $1$ can be represented as $\{\{\}\}$. But what about $2$? Conside www.acmicpc.net 폰 노이만이 자연수를 정의한 것을 차용한 문제입니다. $N$에 대응되는 괄호 문자열의 길이를 $a_{N}$라고 ..
백준 13630번: Buses https://www.acmicpc.net/problem/13630 13630번: Buses The input contains a single line, containing three integers N, K and L, representing respectively the total length, in meters, of the line Ricky is considering, K indicates the number of different colors for micro-buses, and L represents the number of diff www.acmicpc.net 문제를 잘 읽으면 결국 $1 \times N$ 직사각형을 $1 \times 5$, $1 \times 10$ 블록으로 타일링하는 방법..

티스토리툴바