[BOJ-13301]타일장식물

DP ; 동적계획법 문제였다.

타일은 가로x세로 1x1 부터 시작하여 

첫번째타일은 1x1

두번째타일은 1x1

세번째타일은 2x1

네번째타일은 4x1

...

n번째 타일이 깔렸을 때, 타일의 전체둘레를 구하는 문제

 

n번째 타일의 크기는 위 식을 따르며, 

이제 출력으로 전체 타일의 둘레를 구해야한다.

전체 타일의 둘레는 

이며

추가된 n번째 타일이 가로 혹은 세로의 최대 길이가 되며

n-1번째 타일, n번째 타일의 합이 가로 혹은 세로의 최대 길이가 된다.

그래서 2*가로 + 2*세로 를 하면 답이 된다.

if __name__ == '__main__':
    n = int(input())
    ans = list([0,1,1])
    for i in range(3,100): 
        ans.append(ans[i-1]+ans[i-2])
    print(4*ans[n]+2*ans[n-1])