[Programmers] - 2 x n 타일링

문제

문제를 보자마자 수학적 문제인 것을 알았다.
피보나치 문제이다.
하지만 n의 수가 60000 이하인 것을 봤을 때
메모이제이션 문제이다.

코드

#include <string>
#include <array>

using namespace std;

int solution(int n) {
	array<int, 60001> memoi = {0, 1, 2};

	int answer = 0;

	for (int i = 0; i <= n; i++) {
		memoi[i] = memoi[i - 1] + memoi[i - 2];
		memoi[i] %= 1000000007;
	}
	
	return memoi[n];
}

요약

• 예전 memoization을 공부해서 알기만 해놓으면 쉬운 문제이다.
• 재귀를 이용한 피보나치는 크기가 커질 수록 재귀의 크기가 엄청 커지므로
• 배열을 이용해 값만 저장하면 재귀 없이도 가능하다.