[C언어] 백준 1904 : 01타일

생각의 흐름

문제를 보고 이게뭔가 싶었다. 일단 무작정 1부터 6까지 써봤다.
1 = 1, 2 = 2, 3 = 3, 4 = 5, 5 = 8, 6 = 13
5까지 했을때 설마 피보나치인가 싶었는데 6에서 13이 나온 걸 보고 아 피보나치구나 싶었다.
피보나치를 동적 계획법 활용해서 푸는건 해봤기때문에,출력조건에 15746을 나눈 나머지를 출력한다. 이것만 생각하면 된다.

내가 푼 코드

#include <stdio.h>

int arr[1000001];

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

int main()
{
	int n;
	scanf("%d", &n);
	fibo(n);
	printf("%d", fibo(n));
}

15746를 위에다 한 이유는 처음에 printf에 해줬다가 오버플로우가 났다.
n값이 커질수록 피보나치수는 무지막지하게 커지는데 당연하다. 그래서 배열에 넣을 때 나머지를 구한 다음에 넣어주었다.

아 그리고 재귀연습하려고 재귀를 사용했다.