pushback

자.. 나왔다. 큰 수로 나눈 나머지를 출력하라는 문제.

지금이야 DP문제인 것을 알고 풀지만, 이 문제처럼 어떤 수로 나눈 나머지를 출력하는 문제는 DP로 풀릴 확률이 매우 높다.

1과 00을 갖고 N자리의 이진 수열의 개수를 구하는 것이 목표이다.

잘 모르겠으면 일단 적어보자. 어떤 "규칙"을 발견할 지도 모르니...

1자리 : 1 - 1개

2자리 : 00, 11 - 2개

3자리 : 001, 100, 111- 3개

4자리 : 0000, 0011, 1001,  1100, 1111- 5개

5자리 : 00001, 00100, 00111, 10000, 10011, 11001, 11100, 11111 - 8개

6자리 : 000000, 000011, 001001, 001100, 001111, 100001, 100100, 100111, 110000, 110011, 111001, 111100, 111111 - 13개

1, 2, 3, 5, 8, 13 ... ? 익숙하다. 앞에 1이 빠진 피보나치 수열이다.

피보나치인 거 발견했으니까 점화식을 갖고 코딩하면 끝이긴 하지만.. 뒤가 좀 구리다.

정말 정말 정말 우연히 6자리까지 피보나치 수열을 만족하고 7자리부터 다른 수가 나올 수도 있지 않나 ?

당신의 생각이 맞다. 그래서 "왜" 피보나치인지 알아보자.

N자리의 모든 이진 수열은 1 또는 00으로 시작한다.

다시 말하면, 1 또는 00 뒤에 1 또는 00을 붙여 N자리의 이진수를 만드는 것이다.

또 다시 말하면, N자리의 이진수를 만들기 위해서 N-1자리 이진수 뒤에 1을 붙이거나 N-2자리 이진수 뒤에 00을 붙이면 된다.

그렇기 때문에 \(a_n\)을 n자리의 이진수라고 하면, \(a_n = a_{n-1} + a_{n-2}\) 이라는 점화식을 만들 수 있다.

어 근데 N-1자리 이진수 뒤에 1을 붙인 수와 N-2자리 이진수 뒤에 00을 붙인 수가 같은 경우는 생각 안하나요 ?

네. 그런 경우는 나올 수 없습니다.

이유를 수학적으로 풀어보자.

이진수 뒤에 1을 붙이는 행위 = 십진수 x 2 + 1

이진수 뒤에 00을 붙이는 행위 = 십진수 x 4

위에 두 식이 이해가 안된다면 직접 한번 이진수 100에 1이나 00을 붙이고 십진수로 표현해보면 된다.

깨알 상식으로 이진수를 왼쪽으로 한번 Shift하는 것은 곱하기 2를 해주는 것과 같은 효과임을 생각해주면 된다.

(그래서 고인물들이 가끔 더 빠른 연산을 위해 x * 2 보다 x << 1을 선호하는 경우도 있다.)

자 그럼 여기 어떤 정수 \(x, y\)가 있다.

\(x\)에는 1을 붙이고 \(y\)에는 00을 붙이면, 각각 \(2x + 1, 4y\)가 된다.

이제 우리는 \(2x + 1 = 4y\)를 만족시키는 정수 \(x, y\)를 찾아야 한다. 그래야 같은 수가 나올 수 있다는 것이 증명된다.

식을 \(x\)에 대해 살짝 정리하자.

\(x = 2y - \frac{1}{2}\)

음... \(y\)에 어떤 정수를 넣든 \(-\frac{1}{2}\)에 의해 \(x\)는 정수가 나올 수 없음을 알아버렸다.

결국, 우리는 사전에 생각해놨던 피보나치 수열로 이 문제를 해결하면 된다 !

단, 15746으로 나눈 나머지를 출력해야한다는 것을 유의하면서.

여기서 15746으로 나눈 나머지는 또 어떻게 처리하지?라고 생각할 수도 있는데, 정수론에 의해 그냥 모든 결과를 15746으로 나눈 나머지로 저장해주면 된다 ㅎㅎ

코드로 한번 보자.

#include <bits/stdc++.h>
using namespace std;

int fibo[1000001];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int n;
	cin >> n;

	fibo[1] = 1;
	fibo[2] = 2;
	// 매번 15746으로 나눈 나머지를 저장
	for (int i = 3; i <= n; i++) fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 15746;

	cout << fibo[n];

	return 0;
}