백준 1904번

1904번

👍 문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다.
그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다.
결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다.
예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다.
(01, 10은 만들 수 없게 되었다.)
또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다.
단 타일들은 무한히 많은 것으로 가정하자.

👍 입/출력

입력 : 자연수 N (1 ≤ N ≤ 1,000,000)
출력 : (만들 수 있는 2진 수열 개수) % 15746

👍 내 마음대로 해설

왜 피보나치 수열인가?

• N일 때의 경우의 수는
  (N-2일 때 경우의 수들의 조합 + 00을 더하는 조합)과
  (N-1일 때 경우의 수들의 조합 + 1을 더하는 조합)을 더한 것이기 때문

N-1 조합일 때는 해당 조합에 1을 더하거나 0을 더할 수 있는데
0은 짖궂은 동주의 트롤로 연속된 00밖에 사용할 수 없다

N-2 조합일 때

• 10을 붙이면 0 하나 타일을 붙이는 것과 다름없으니 될 수 없는 조합
• 01을 붙이는 것 또한 N-2 조합에 1로 끝나는 숫자가 있을 시 성립할 수 없으며
  0으로 끝나더라도 0이 홀수 개가 연속될 것이기에 성립 불가
• 11을 붙일 경우 이전의 N-1 조합에 1로 끝나는 경우에 1을 붙인 것과 동일 결과로서
  중복될 수밖에 없으므로 이것 또한 성립 불가(내가 실수한 부분)
• 그렇기에 00을 붙이는 조합밖에 되지 않는다.

그렇기에 피보나치 수열이 적용된다.

👍 c++ 정답 코드

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

long long fibo[1000001];
void init() {
	fibo[1] = 1;
	fibo[2] = 2;
}

int main() {
	init();
	int N;
	cin >> N;
	for (int i = 3; i <= N; i++) {
		fibo[i] = (fibo[i - 1] + fibo[i - 2])%15746;
	}

	cout << fibo[N] << '\n';
}

재귀 호출을 왜 안씀?
재귀 호출을 사용할 경우
fibo(N)을 구하기 위해 호출하면 fibo(N-1), fibo(N-2)를 호출해야하고
fibo(N-1)을 계산하기 위해 fibo(N-2), fibo(N-3)을 호출
fibo(N-2)를 계산하기 위해 fibo(N-3), fibo(N-4)를 호출하는 등
같은 계산을 위해 중복된 호출이 수행되어 연산이 느려지게 된다
시간 복잡도 : O(2ⁿ)이 되버림

반면 동적 프로그래밍을 사용하면
했던 계산을 또 안해도 되기에
시간 복잡도 : O(N)밖에 걸리지 않음

아니, 근데!!!

피보나치를 더해갈 때마다 모듈러 연산을 수행하면 계산 결과가 잘못되지 않을까?
but 모듈러 연산은
(A+B)modC의 나머지나
(AmodC + BmodC)modC의 나머지가 같은 특징이 존재하기에
문제가 되지 않음.