[C++] 백준 1904번 : 01타일

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

1904번: 01타일

---

문제 풀이

 n자릿수일 때 만들 수 있는 모든 가짓수는 피보나치 수열이다.

자릿수	개수
1자리	1개
2자리	2개
3자리	3개
4자리	5개
5자리	8개
6자리	13개

 

함수는 피보나치수열을 구현하면 된다. 시간을 줄이기 위해서 배열에 값을 저장해서 불러오는 방식으로 구현한다.

정답이 15746으로 나눈 나머지를 구하는 것인데 단순히 계산하면 n값이 50만 넘어가도 잘못된 값이 출력된다.

따라서, 함수 fibo에서 값을 리턴할 때도 15746으로 나눈 나머지와 main 함수에서 출력할 때도 15746으로 나누어 잘못된 값이 출력되는 것을 막는다.

느낀 점

 처음에 어떻게 구현할지 고민하다가 이웃하는 경우의 수를 따지는 것으로 n = 5 일 때, n = 6 일 때 차근차근 확인하다가 피보나치수열인 것을 찾아냈다. 이게 키였구나! 하고 바로 제출했는데 틀리길레 살짝 당황했다. 이내 15746이란 숫자가 괜히 있는 게 아님을 알고 바로 수정했다.

코드

#include <iostream>

using namespace std;
int n;
int arr[1000001] = { 1,2, };

int fibo(int n) {
	if (n == 1 || n == 2) return arr[n - 1];
	else if (arr[n - 1] == 0) arr[n - 1] = fibo(n - 1) + fibo(n - 2);
	return arr[n-1] % 15746;
}

int main() {
	cin >> n;
	long long result = fibo(n) % 15746;
	cout << result;
}