프로그래머스] C++ 동적계획법(Dynamic Programming) - 타일 장식물(level 3)

해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다.

아래 링크를 통해 풀 수 있습니다.

https://programmers.co.kr/learn/courses/30/lessons/43104

1. 문제

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

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

타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.

제한 사항

• N은 1 이상 80 이하인 자연수이다.

입출력 예

N	return
5	26
6	42

2. 조건

1. 그림과 같이 피보나치 수열을 직사각형으로 표현했을 때 해당 수는 직사각형의 둘레가 된다.

2. N번째 숫자까지 직사각형을 이어 붙였을 때 총 직사각형의 둘레를 구하여라.

3. 풀이

간단한 문제입니다.

피보나치 수열을 N번째 까지 구한 후 둘레를 구해주면 됩니다.

여기서 패턴이 존제하는데, N번째 까지 직사각형을 구한다면 (N둘레 + N-1둘레 )* 2 입니다.

그림을 보면 알겠지만 가로의 길이와 세로의 길이는 계속 변하지만 한변은 N + N - 1이 되고

다른 한변은 N이 됩니다. 직사각형의 둘레의 길이는 (가로 + 세로) * 2 이므로 피보나치 수열을 구한 후

계산해 주면 됩니다.

4. 코드

#include <string>

#include <vector>

using namespace std;

long long solution(int N) {

    long long answer = 0;

    vector<long long> v(2, 1);

    

    for(int i = 1; i <= N; i++)

        v.emplace_back(v[i] + v[i - 1]); 

    

    answer = (v[N] + v[N - 1]) * 2;

    return answer;

}