본문 바로가기

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

 (108)
백준 27875번: 파이파이 https://www.acmicpc.net/problem/27875 27875번: 파이파이 첫째 줄에 $n$이 주어진다. $(1\le n \le 314\,159)$ www.acmicpc.net 인터넷 검색으로 어떻게든 레퍼런스를 찾기만 하면 매우 쉬워지는 문제였습니다. 일반적으로 어떤 실수 $x$의 소수점 아래 $N$번째 수를 구하기 위해서는 $10^{N} \times x$을 관찰합니다. 이 문제에서 $\pi ^{2}$의 소수점 아래 $N$번째 수는, 16진법이므로, $16^{N} \times \pi ^{2}$를 얻어야 할 것입니다. 여기서 $\pi ^{2}$의 16진법 표현을 얻는 방법이 문제의 핵심이었습니다. $\pi$의 16진법 표현을 안다면 어쩌면 가능할 수도 있습니다만 소스 코드 길이 제한에 걸..
백준 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(..
백준 27318번: 세상에서 가장 달달한 디저트 만들기 (matrix) https://www.acmicpc.net/problem/27318 27318번: 세상에서 가장 달달한 디저트 만들기 한별이는 튀르키예와 그리스의 전통 젤리인 로쿰을 만들고 있다. 로쿰은 녹말, 물, 설탕, 레몬즙 등을 냄비에 넣고 끓여서 걸쭉해질 때까지 저어준 다음, 겉에 슈가파우더를 뿌려서 굳히는 디저 www.acmicpc.net 문제에서는 $N$과 $M$이 달라질 때마다 완전히 꽉 차있는 $\left ( N^{M} \right )^{3}$짜리 정육면체로부터 시작하지만, 어차피 최종 결과물은 $N,M$값에 상관없이 부피 1짜리 정육면체들로 이루어져있습니다. 즉, $N$을 고정시킨 뒤, $M$을 하나씩 늘리며 이전 단계의 로쿰이 몇 번 나타나는지 확인하는 게 떠올리기 쉬운 풀이 같습니다. 그림으로 주어..
백준 25028번: Fully Generate https://www.acmicpc.net/problem/25028 25028번: Fully Generate 양의 정수 만으로 이루어진 단조 증가 수열 $G$가 있다. 이 수열에서 $G_i$는 $i$가 $1$ 이상의 정수일 때 정의되며, $G$에서 $i$가 등장하는 횟수를 나타낸다. 정확히 말하면, $G$는 $i$가 $G_i$번 나타나 www.acmicpc.net 풀이를 설명하기가 상당히 난해한 문제라고 생각합니다. 우선, 글에 나오는 수열은 Golomb Sequence 등으로 불리며 Wikipedia, OEIS에 문서가 있습니다. 가장 단순한 풀이는 물론 $G_{i}$를 모두 구하는 것입니다. 이는 append같은 메서드를 지원하는 컨테이너를 써서 쉽게 구현할 수 있는데, space complexity..
백준 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..
백준 18151번: DivModulo https://www.acmicpc.net/problem/18151 18151번: DivModulo Modulo (mod) is a very common operator on integers. For two integers n and d with d > 0, r ≡ (n mod d) is defined where 0 ≤ r < d and there exists an integer q, such that n = q × d+r. For example, (200 mod 5) ≡ 0 means that the remainder of 200 divi www.acmicpc.net 정수론에 대한 지식이 부족한 저로서는 매우 힘든 문제 중 하나였습니다. 처음에는 Lucas' Theorem과, Andrew Granvil..
백준 10909번: Quaternion inverse https://www.acmicpc.net/problem/10909 10909번: Quaternion inverse 각 \(A\)가 주어질 때마다, \(AB = 1\)을 만족하는 \(B = a + bi + cj + dk\)들 중 하나를 나타내는 네 개의 정수 \(a\), \(b\), \(c\), \(d\)를 공백으로 구분하여 \(T\) 줄에 걸쳐 출력하면 된다. 만약 이런 \(B\)가 www.acmicpc.net 사원수, quaternion이라는 낯선 대상이 주어졌을 뿐, 실제로는 복소수의 역원을 구하는 것과 크게 다르지 않습니다. 일반적인 사원수에 대해 역수를 구하는 방법은 다음 링크 와 같이 주어집니다. 다시 말하면, 다음 식이 성립합니다. $$ \times < a-bi-c..

티스토리툴바