본문 바로가기

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

 (8)
[C++] 11440번 피보나치 수의 제곱의 합 / 28749번 Квадраты Фибоначчи https://www.acmicpc.net/problem/11440https://www.acmicpc.net/problem/28749 25/03/04 25/03/09  두 문제는 인덱스만 다르고 동일한 문제이므로, 같은 풀이 방법으로 설명하겠다. 문제 접근 방식:  피보나치 수의 거듭 제곱의 합을 구하는 문제이다. $F_{n} = F_{n-1} + F_{n-2}$를 생각해보자. 제곱을 하면 다음과 같다. $$\begin{align}{F_{n}}^{2} &= (F_{n-1} + F_{n-2})^{2} \\ &= {F_{n-1}}^{2} + {F_{n-2}}^{2} + 2F_{n-1}F_{n-2}\end{align}$$ 제곱 항은 공통이 되는데, 뒤에 붙은 $2F_{n-1}F_{n-2}$항이 공통이 되지 않..
[Python] 32390번 과녁 맞히기 https://www.acmicpc.net/problem/32390 24/11/17  이전에 KCPC때 검수 못했던 문제 중 하나인데, 이제서야 풀어본다. 사실 그때 한 30분 정도 생각해보다가 답이 안나와서 그냥 GG치고 다른 문제를 봤다. 이제서야 붙잡은 이유는 큰 이유는 없고, 그냥 좀 붙잡으면 풀릴 것 같아서 붙잡았다. 이 문제를 풀기 위해선, 모듈로 곱셈 역원에 대한 지식이 필요하다. 문제 접근 방식:  문제가 뭔가 수능에서 나올법 한 경우의 수 문제랑 비스무리 하다. $M$개의 줄이 있고, 각 줄에는 과녁이 $A_i$개 만큼 달려있다. 나는 과녁을 쏠 때, 각 줄에서 위 또는 아래만 쏠 수 있다.이 문제에서 구하고자 하는 것은 과녁을 쏘는 전체 경우의 수이다.  일단 각 줄 별로 생각을 하면,..
[Python] 13172번 Σ https://www.acmicpc.net/problem/13172 24/05/29  클래스에 있던 문제 중에 하나로, 간단한 정수론 문제이다. 문제 접근 방식:  친절하게도, 문제에 대한 답이 다음과 같이 써져있다. $$\frac{S_1}{N_1} + \frac{S_2}{N_2} + \cdots + \frac{S_M}{N_M}$$ 이를 그대로 구현해주면 된다. 이때, 답은 기약분수로 나타내야 하므로, $S_i$와 $N_i$를 입력받을 때마다, $\text{gcd}(S_i, N_i)$로 두 수를 나눠준다. 또한, 모듈로 역원은 파이썬에서는 pow함수의 지수부분에 -1을 넣음으로써 쉽게 구할 수 있으므로 이를 활용하면 쉬워진다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 ..
[Python] 12850번 본대 산책2 https://www.acmicpc.net/problem/12850 23/03/21  예전에 이 문제에 대한 풀이 글을 작성한 것 같았는데, 지금 검색해보니 작성하지 않아서 오랜만에 작성하려고 한다. 그래프를 인접 행렬로 나타낼 수 있는지에 대한 지식과, 그 행렬을 거듭제곱하면 경로의 개수가 나온다는 지식을 요구하는 문제다.  문제 접근 방식:  본대 산책1이 있고 본대 산책2가 있는데, 둘은 제한만 다른 문제다. 본대 산책2는 본대 산책1에 분할 정복을 이용한 거듭제곱 태그가 들어가서 난이도가 더 뛰어버렸다. (사실 그 정도로 어려운가 싶지만, 그렇다고 하자.) 문제에서 주어진 그래프를 인접 행렬의 형태로 바꿔보자.matrix = [[0, 1, 1, 0, 0, 0, 0, 0], [1, ..
[Python] 1160번 Random Number Generator https://www.acmicpc.net/problem/1160 24/04/15  분할 정복을 이용한 거듭제곱 문제이다. 식 정리하는 과정이 조금 까다롭다. 문제 접근 방식:  점화식이 $a_{n+1} = \alpha a_n + \beta$의 꼴이기 때문에, 이를 잘 정리하면 일반항을 얻어낼 수 있다. 식을 다음과 같이 정리해보자. $$\begin{align} X_{n+1} &= aX_n + c \\ X_{n+1} - \alpha &= a(X_n - \alpha) \end{align} $$이때, $X_n - \alpha = Y_n$으로 치환해보자.$$\begin{align} Y_{n+1} &= aY_n \\ Y_n &= a^{n-1} Y_1 \\ X_n - \alpha &= a^{n-1}(X_1 - \..
[Python] 31478번 포니 양은 놀고 싶어! https://www.acmicpc.net/problem/31478 31478번: 포니 양은 놀고 싶어! 첫 번째 줄에 정수 $A$, $B$, $C$가 주어진다. ($1\leq A < 7$, $1\leq B, C \leq 10^{9}$, $B^C$는 $A$의 배수) 두 번째 줄에 정수 $K$와 $L$이 주어진다. ($0\leq K,L < 7$) www.acmicpc.net 24/04/15 간단한 정수론 문제입니다. 분할 정복을 이용한 거듭제곱에 관한 지식과, 페르마의 소정리에 관한 지식이 있어야 해결할 수 있습니다. 문제 접근 방식: 결국 $A^{B^C}$와 $B^C / A$를 빨리 구하는 문제로 귀결됩니다. 후자는 빠르게 구할 수 있습니다. 결국 $7$일이라는 범위 안에서만 따지는 것이기 때문에 $7$..
[Python] 12445번 バクテリアの増殖 (Small) https://www.acmicpc.net/problem/12445 12445번: バクテリアの増殖 (Small) 微生物の研究者であるパスカルは、特殊な増殖の傾向を示すバクテリアを発見した。どうやらそのバクテリアは、ある時点で x 個存在したとすると、理想的な環境下では1時間後に xx 個に増 www.acmicpc.net 24/02/09 아주 아주 간단한 문제로, 파이썬으로 해결하기에 아주 적절한 문제다. 문제 접근 방식: 이 문제는 Small버전이 존재하고 Large버전이 존재한다. Large버전의 경우, Power tower류의 문제로, 정수론을 배워야 풀 수 있는 문제다. https://www.acmicpc.net/problem/13970 13970번: Power towers In this example, as M =..
[Python] 1629번 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 22/09/21 파이썬의 강력함. 그 한 줄이면 충분하다. 문제 접근 방식: 파이썬의 기본 내장 함수 중 pow함수는 어떤 숫자를 거듭제곱한 것을 특정 숫자로 나누는 연산을 지원한다. 또한, 기본적으로 pow함수의 거듭제곱의 원리가 분할 정복을 이용한 거듭제곱이라 매우 빠르다. 제일 그 풀이가 간단해서 그 풀이로 문제를 풀었다. 이후에 만약 행렬 거듭제곱문제를 풀게 된다면 새롭게 함수를 구현해야 하긴 한다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드..

티스토리툴바