백준 2133 타일 채우기(DP)

2133번: 타일 채우기

 

 

3 x 2 일땐 이렇게 총 3가지가 나온다

 

1x2. 2x1로만 타일을 만들어야하기 때문에 홀수개의 타일의 경우는 채울 수 없으므로 N이 홀수일 땐 불가하고

 

이런식으로 이어갈텐데

 

N = 4부터 가운데에 영향을 주는 애들이 하나씩 생기기 시작한다. 이런 경우를 모두 찾아서 더해주면 된다

for (int i = 4; i < 31; i+=2) {
    dp[i] = dp[i-2] * 3;
    for (int j = i-4; j >=0 ; j-=2) {
        dp[i] += dp[j] * 2;
    }
}