백준_01타일

[ 해결 방법 ]

N을 몇 개 진행해보니까 피보니치 수열임을 알았다. 피보나치를 구현할 때 재귀로 구현하면 안된다. 이렇게 구현하면 불필요한 재귀를 호출하기 때문에 메모리 초과가 난다.

fibo(10)

          fibo(9)                         fibo(8)

fibo(8)          fibo(7)   fibo(7)    fibo(6)

위에 그림처럼 fibo(8), fibo(7)을 이미 구했는데 불필요하게 호출한다. N이 커질 수록 이런 일은 더 많이 발생한다.

생각해보면 피보나치는 fibo(n) = fibo(n-1) + fibo(n-2)이기 때문에 현재 값을 구하기 위해서 2개의 수만 알면된다. 이전값과 그 이전값. 그래서 변수 3개만 있으면 피보나치를 효율적으로 구현할 수 있다.

마지막으로 모듈러연산의 성질을 이용한다.

성질 1 : (a + b) % n = ( a % n + b % n) % n

성질 2 : (a - b) % n = ( a % n - b % n) % n

성질 3 : (a x b) % n = ( a % n x b % n) % n

성질 4 : 10^n % n = (10 % n)^n % n

우리는 성질1을 다음처럼 이용한다. 

Fibo(n) % 15746 = ( Fibo(n-1) % 15746 + Fibo(n-2) % 15746 ) % 15746

아래의 코드와 바로 매칭이 안된다. 조금만 생각해보면 아래와 같다.

아래 코드에서 c = (a + b) % 15746은 위 식에서 바깥쪽 % 15746이 적용된다.

a = b; b = c는 위 식에서 안 쪽 % 15746이 적용된다.

[ 코드 ]

#include <stdio.h>

int main()
{
	int N;
	int a = 1, b = 2, c;
	scanf("%d", &N);
	for (int i = 3; i <= N; i++)
	{
		c = (a + b) % 15746;
		a = b;
		b = c;
	}
	printf("%d\n", c);
	return 0;
}