타일 장식물

#include <string>
#include <vector>
 
using namespace std;
 
long long dp[80] = {0};
 
long long solution(int N) {
    if(N == 1) return 4;
    dp[0] = 1;
    dp[1] = 1;
    
    for(int i = 2; i < N; i++) 
        dp[i] = dp[i - 1] + dp[i - 2];
    
    return (dp[N - 1] + dp[N - 2] + dp[N - 1]) * 2;
}

이 문제는 다이나믹 프로그래밍으로 풀면 된다.

다이나믹 프로그래밍으로 풀기위해서는 먼저 일반적인 식을 구해야한다. 그 식을 구하기 위해서 위의 문제를 살펴보면 처음 두개는 1,1으로 반복이지만 다음번부터는 일정한 규칙이 일어남을 알 수 있다. 예를들어 1에서 2로 넘어가는 시기를 보자. 이는 처음 1, 두번째 1을 더해서 2가 나옴을 알 수 있다. 그리고 그 다음 2에서 3으로 넘어가는 과정은 3이전의 두개의 사각형 1, 2를 더하면 됨을 알 수 있다. 이렇게 n번째의 한변의 길이를 알고 싶을 때는 n - 1번째와 n - 2번째의 길이를 더하면 되는 것이다. 이것을 일반화하면 dp[n] = dp[n-1] + dp[n-2]가 된다는 것이다. 이를 이용해서 둘레도 구할 수 있다.

둘레를 구하기 위해서 위의 문제를 다시 보면 n번째 사각형의 한변의 길이와 n - 1번째 사각형의 한변의 길이를 더한다음 다시 n번째 사각형의 한번의 길이를 더해서 2를 곱해주면 나옴을 알 수 있다. 

예를 들어 문제에 주어진 5번째에 해당하는 둘레를 구해보자. 5번째 사각형의 한변의 길이는 5이다. 그리고 4번째 사각형의 한변의 길이는 3이다. 5 + 3을 해주면 사각형의 가로 길이가 나온다. 거기에 5번째 사각형의 한변의 길이, 즉 세로 길이를 더해주면 둘레의 절반에 해당하는 것이다. 마지막으로 둘레를 구하기 위해 2를 곱해준다.  

이제 이를 코드로 표현을 해보자.

처음에 N이 1이 나오면 그냥 4를 반환해주도록 하였다. 그 이유는 첫번째 사각형의 둘레는 4이기 때문이다. 이 이후에는 dp[0]과 dp[1]를 1로 초기화시켜주고 반복을 해주면서 위에서 구한 식을 그대로 적용시켜주면 된다. 즉 dp[i]값에 dp[i - 1] + dp[i - 2]를 해주면 되는 것이다. 하지만 주의해줘야할 것은 첫번째의 인덱스는 0이란 것을 명심해줘야한다. 인덱스와 n번째 사각형을 일치시켜주려면 dp[0]에 0을 넣으면 될 것 같다.

마지막으로 값을 반환해줄때는 둘레를 반환해줘야하기 때문에 dp[N - 1] + dp[N - 2] + dp[N - 1]을 해준이후 이 값에 2를 곱해줘서 반환해준다.