프로그래머스 43104 - 타일 장식물 (c++)

프로그래머스 43104 - 타일 장식물

문제 링크

생각 및 접근

• 우선, 정사각형의 갯수에 따라 정사각형의 길이가 얼마나 길어지는지 살펴보아야 한다.

  • 1, 1, 2, 3, 5, 8, ...
  • 누가 봐도 이건 피보나치 수열이다.

• 문제에서 N이 주어지면, 일단 피보나치 수열을 통해 정사각형 길이를 구하고, 그 값을 토대로 직사각형의 길이를 구하면 된다.
  

  

• 직사각형 길이는 점화식으로 나타내면 length(n) = 4 * square(n) + 2 * square(n - 1)이 된다.

코드

#include <bits/stdc++.h>
using namespace std;

long long tiles[81];

long long dp(int N){
    if(N == 1 || N == 2)    return tiles[N] = 1;
    else if(tiles[N] == 0)  return tiles[N] = dp(N - 1) + dp(N - 2);
    else                    return tiles[N];
}

long long solution(int N) {
    return 4 * dp(N) + 2 * dp(N - 1);
}

채점 결과