백준 C++ 1904번) 01타일

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

1904번: 01타일

 

이건 수를 나열해보면 공식을 찾아볼 수 있습니다.

 

1 = 1

2 = 2

3 = 3

4 = 5

5 = 8

6 = 13

 

이걸 보면 N(n) = N(n-1) + N(n-2) 인 것을 볼 수 있습니다. 따라서 그걸 코드로 구현해주면 됩니다. 단, 숫자가 크기 때문에 자료형을 잘 선택해주어야 합니다.

 

#pragma warning(disable:4996)
#include<stdio.h>

long long num[1000001] = { 0,1, 2, 3, };
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 3; i <= n; i++) {
		num[i] = (num[i - 1] + num[i - 2])%15746;
	}
	printf("%lld\n", num[n]);
}