[C++][알고리즘] 프로그래머스:: 타일장식물

피보나치 & 메모이제이션(DP)

피보나치 수열로 생기는 타일 도형의 사각형 둘레를 계산하면 된다.

피보나치 수열의 범위가 80까지 이므로 메모이제이션을 활용하지 않으면 시간초과가 뜰것이라 생각해서 

메모이제이션을 활용하여 문제를 풀었다.

 

	#include <string>
	#include <vector>
	#include <iostream>
	using namespace std;
	long long memo[81]={0};
	long long pibo(int N)
	{
	if(N==1 || N==2)
	{
	return memo[N];
	}
	else if(memo[N]!=0)
	{
	return memo[N];
	}
	else
	{
	memo[N] = pibo(N-2) + pibo(N-1);
	return memo[N];
	}
	}
	long long solution(int N) {
	long long answer = 0;
	memo[1]=1;
	memo[2]=1;
	answer = pibo(N);
	answer = (memo[N-2] + memo[N-1]*2 + memo[N]) *2;
	return answer;
	}

view raw tile.cpp hosted with ❤ by GitHub

후기

다른사람 풀이보니까.. 진짜 똑똑한 사람들 많구나 싶다.

10줄이내로 해결이 되네...