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

문제 설명 

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다.

타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다. [1, 1, 2, 3, 5, 8, .] 지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다. 타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.

입출력 예

N : 5 return : 26

N : 6 return : 42

풀이 과정

피보나치 생각하시면 됩니다.

An=An-1+An-2를 이용해서

배열에 넣어서 풀었습니다.

문제는 프로그래머스에서 효용성 검사가 항상 걸렸는데 아마도 매우 큰 수를 넣기 때문에 값을 더하는 곳에 int를 쓰면 숫자가 초과되서 오류가 걸릴 것입니다.

그래서 vector만들 때 int쓰지 마세요

소스 코드

#include <vector>
using namespace std;

long long solution(int N) {
	long long answer = 0;
	vector<long> temp;
    temp.push_back(0);
    temp.push_back(1);
	if (N == 1) {
		return 4;
	}
	else 
		for (int i = 2; i < N+1; i++) {
			temp.push_back(temp[i-2]+temp[i-1]);
		}
	answer = temp[N] * 4 + 2 * temp[N-1];
	return answer;
}