직장인의 개발 일기

https://www.acmicpc.net/problem/2749

[ 문제풀이 ]

1. 아래의 식을 바탕으로 $F_{n}$의 값을 구할 수 있습니다.

$\begin{pmatrix}
1 &  1\\
1 &  0\\
\end{pmatrix}^{n} = \begin{bmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1} \\
\end{bmatrix}$

2. 분할 정복을 활용하여 n이 2의 배수라면 $F_{n} = F_{\frac{n}{2}}\times F_{\frac{n}{2}}$ 아니라면 $F_{n-1}\times F_{1}$을 통해 구해줍니다.

3. 메모이제이션을 활용하여 각각의 $F_{i}$을 1,000,000으로 나눈 나머지 값을 저장합니다.

4. $F_{n}$의 [0, 1] 항을 출력해 줍니다.

[ 소스코드 ]

https://www.acmicpc.net/problem/17401

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/38

위 글의 문제 풀이 방식과 매우 비슷하지만 행렬이 매번 바뀌고, 바뀐 행렬에 따라 풀이 방법이 달라집니다.

1. 각각의 행렬을 모두 곱한 all 행렬과 나머지 행렬들을 곱한 remain 행렬을 만듭니다.

2. 분할 정복을 통해 구한 ans와 remain 행렬을 곱합니다.

[ 소스 코드 ]

https://www.acmicpc.net/problem/1629

[ 문제풀이 ]

가장 기본적인 분할 정복 문제입니다. 제곱수의 값이 짝수이면 제곱수를 반으로 나누어 서로 곱하는 방식으로 진행하여 시간 복잡도를 O(logN)으로 줄일 수 있습니다. 시간을 더 단축하기 위해서 메모제이션을 해주어야 문제를 풀 수 있습니다.

[ 소스 코드 ]

https://www.acmicpc.net/problem/11444

[ 문제풀이 ]

분할 정복과 도가뉴의 방정식을 이용하면 쉽게 풀 수 있는 문제입니다. 또한 시간 초과를 방지하기 위해서 메모제이션을 해주어야 하는데 n의 값이 매우 크므로 unordered_map을 활용하여 문제를 풀었습니다.

도가뉴의 방정식은 다음과 같습니다.

$a_{2n}=a_{n}(a_{n} + 2a_{n-1})$

$a_{2n-1}=a_{n}^{2}+a_{n-1}^{2}$

[ 소스 코드 ]

https://www.acmicpc.net/problem/10830

[ 문제풀이 ]

일반적인 분할 정복 문제와 똑같이 풀면 됩니다!

제곱수 n이 짝수일 때 $A^{\frac{n}{2}}\times A^{\frac{n}{2}}$ 홀수일 때 $A^{n-1}\times A$의 방식으로 계산해나가면 O(logn)의 시간 복잡도로 풀 수 있습니다.

[ 소스 코드 ]

https://www.acmicpc.net/problem/13977

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 걸 추천드립니다.

https://rudalsd.tistory.com/61?category=1064608 

먼저 $\binom{N}{K}$는 다음과 같이 나타낼 수 있습니다.

$\binom{N}{K} = \frac{N!}{(N-K)!K!}$

그리고 페르마의 소정리를 이용하여 mod $m$에서 어떤 수를 $a$로 나눈다는 뜻은 $a$의 역원을 곱한다는 뜻과 같습니다. 따라서 $m$이 소수일 때, $a^{m-1}\equiv 1($mod $m)$이고, $a\times a^{m-2}\equiv 1($mod $m)$이므로 mod $m$에서 $a$에 대한 곱셈의 역원은 $a^{m-2}$입니다.

따라서, 

$\frac{N!}{(N-K)!K!} \equiv N!\times ((N-K)!K!)^{m-2}($mod $m)$

이 됩니다.

분모의 수로 나누는 방법 대신 $m-2$제곱한 값을 곱해주면 모듈러 연산 시 같은 결과가 나오는 것을 알 수 있습니다.

이 때 $m$의 값이 $1,000,000,007$로 매우 크므로 분할 정복을 이용한 거듭제곱을 이용하여 문제를 풀어주면 됩니다.

[ 소스 코드 ]

https://www.acmicpc.net/problem/15824

[ 문제풀이 ]

이 문제에서는 모듈러 연산이 필요하므로 다음 글을 읽고 오시면 좋습니다!

https://rudalsd.tistory.com/45?category=1064608 

어떤 한 수가 조합 내에서 최댓값이 될 때의 개수와 최솟값이 될 때의 개수를 통해 쉽게 정답을 구할 수 있습니다.

먼저 입력받은 수를 오름차순으로 정렬한 후 for문을 돌면서 그 수가 최댓값이 될 때의 조합의 개수는 그 수보다 작은 수의 개수가 i일 때 2^i가 됩니다. 

마찬가지로 그 수가 최솟값이 될 때의 조합의 개수는 그 수보다 큰 수의 개수가 j일 때 2^j가 됩니다.

따라서 모든 수에 대해 (2^i - 2^j) * a를 구해서 더해주면 됩니다.

하지만 n의 최댓값이 300,000이므로 일반적인 방법으로는 2^300,000의 수를 구하기는 쉽지 않습니다. 따라서 분할 정복을 활용하여 답을 구해줍니다.

[ 소스 코드 ]

https://www.acmicpc.net/problem/12850

[ 문제풀이 ]

준영이가 정보관에서 1분 후 이동할 수 있는 건물은 전산관과 미래관입니다. 또한 전산관에서 1분 후 이동할 수 있는 건물은 신양관, 미래관 그리고 정보관입니다. 이를 행렬로 표현하면 다음과 같습니다.

그렇다면 각 건물에서 2분 후 이동할 수 있는 건물은 어떻게 구할 수 있을까요? 바로 1분 후 이동할 수 있는 건물들에 대한 행렬을 서로 곱하면 됩니다.

따라서 n분 후 이동할 수 있는 건물을 구하는 방법은 다음과 같습니다.

n % 2 == 0 일 때

mat( n / 2 ) * mat( n / 2 )

n % 2 == 1 일 때

mat( n - 1 ) * mat( 1 )

재귀를 통해 D번 이동했을 때 mat( D )의 0 , 0의 값을 출력하면 정보과학관으로 돌아오는 경우의 수를 구할 수 있습니다.

[ 소스 코드 ]