동적계획법. [11726]

[1. 문제 설명]

[2. 풀이 접근]

완전 탐색에서 시작한다.

맨 왼쪽을 2x1 타일 1개로 채우고, 나머지 2x(n-1) 타일에 대한 부분 문제를 해결한다.
맨 왼쪽을 2x2 타일 2개로 채우고, 나머지 2x(n-2) 타일에 대한 부분 문제를 해결한다.
두 경우의 합을 반환한다.
기저 사례
=> 길이가 0 인 경우: 모든 타일을 채움 => 1을 반환 => 하나의 경우를 완성하였다.
=> 길이가 음수인 경우: 타일을 채울 수 없음 => 0을 반환

이 문제는 최적화 문제는 아니다.

그러나 전체 타일 길이 N에 대해서

앞의 [0, N-A) 를 어떻게 채우던 간에 [N-A, N) 을 채우는 문제는 한번만 계산하면 된다.

그래서 메모이제이션을

현재 채워야 할 타일의 길이에 대한 부분 문제에 대해서 적용 할 수 있다.

[3. 코드]

test_kernelv2