Programmers > 코딩테스트 연습 > 동적계획법 > 타일장식물

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/43104

풀이

처음으로 이런 문제를 만나면 당황할 수는 있겠지만 

숫자들을 쭉 나열하고 규칙성을 찾아보면 생각보다 쉽게 풀릴 수 있다.

타일의 길이들을 처음부터 쭉 나열하면

1 1 2 3 5 8 13..... 이 되고 여기서 memo배열에 이 수를 저장한다고 했을 때

memo[i] = memo[i-3] + memo[i-2] + memo[i-1] 

이런 식을 통해 길이가 도출됨을 알 수 있다.

둘레도 마찬가지 인데 가로 세로가 만들어지는 걸 관찰하다 보면

한 변 a = memo[N-2] + memo[N-1] 이 되고

b = memo[N-1] + memo[N]이 되어

2 * (a + b) 를 하면 답을 도출할 수 있음을 알 수 있다.