[프로그래머스] 타일 장식물

문제  : Level3 타일 장식물

[ 문제출처 ]  https://programmers.co.kr/learn/courses/30/lessons/43104

 

 

[ 문제풀이 ]

 

문제는 다음과 같은 타일이 있을 때

안쪽 타일 부터 시작해서  [1, 1, 2, 3, 5, 8, .... , ] 처럼 점점 타일이 확장된다 

정답은 N개의 타일로 구성된 직사각형의 둘레를 구하는 것이다

 

규칙이 보이지 않는가?  

 

n번째 타일의 한 변의 길이는 밑에 식과 같이 정의가 가능 하다.

 

 

한 변의 길이를 정의하였으니 N번째 타일을 하나씩 붙여 가면서 직사각형 둘레의 길이는 

어떻게 변하는지 살펴보자

 

기존에 있던 빨간색의 타일에서 파란색 타일이 추가된 상황이다

타일의 겹치는 부분의 길이를 파란색 타일의 윗변으로 생각해주고 

즉 왼쪽 오른쪽 양변의 길이만 더해주면 된다

 

기존의 타일의 길이에서 (추가되는 타일의 한 변의 길이 * 2)을 더해주면 

구하 고자 하는 정답을 구할 수 있다

 

 

 

[ 소스 코드 ]

 

#include <string>
#include <vector>
typedef long long ll;
using namespace std;
const int MAX = 80 + 1;
ll side[MAX], ans[MAX];
ll solution(int N) {
    side[0] = 0, side[1] = 1, ans[1] = 4;
    for (int i = 2; i <= N; i++) {
        side[i] = side[i - 1] + side[i - 2];
        ans[i] = ans[i - 1] + (2 * side[i]);
    }
    return ans[N];
}