[JAVA/자바] 백준 2133번: 타일 채우기

문제 우선 N = 2일때의 경우를 생각해보았다. 총 세가지의 경우의 수가 나온다.

즉 dp[2] = 3 N = 3일 때는 타일을 채울 수 없다. 즉 홀수 일때는 경우의 수 0 N = 4일 때를 생각해보면 길이를 2:2 나눴을 때 왼쪽에 3가지, 오른쪽에 3가지 경우의 수가 나온다.

N = 4일때는 위와 같은 경우의 수도 추가되기 때문에 두가지의 경우가 추가된다. 즉 dp[4] = dp[2] * dp[2] + 2 = dp[2] * 3 + 2로 표현 가능 그렇다면 N = 6일 때는?

이쯤 되면 어느정도 규칙이 보인다. 6을 길이 4:2로 나눴을 때 왼쪽 영역에서 dp[4]만큼의 경우의 수가 나오고 오른쪽은 dp[2]만큼의 경우의 수가 나온다. 길이를 2:4로 나..........