https://www.acmicpc.net/problem/2133
시간 2초, 메모리 128MB
input :
- N(1 ≤ N ≤ 30)
output :
- 경우의 수를 출력
조건 :
- 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수
홀수일 때는 타일을 만들 수 없다. 반복문을 2씩 증가하게 만들어야 함.
처음 생각 한 것은 i번째 보다 2적을 때 타일을 채우는 횟수 3.
i 번째 보다 4적을 때 타일을 채우는 횟수 2.
그냥 dp[i - 2] 3 + dp[i - 4] 2 해서 하면은.. 당연히 틀린다.
빼먹은 경우의 수.
n = 6 일 떄,
(n = 2) 2 + (n = 4) 2
ㅡ 자 모양의 타일을 바닥에 다 깔 경우. 아래와 같은 모양을 만들수 있고.
1 12 23 3
4 55 66 7
4 88 99 7
이를 뒤집을 수 도 있기에 2가지 경우가 생긴다.
그래서 위의 식에 2를 더해 줘야 한다.
(n = 2) 2 + (n = 4) 2 + 2
그렇다면 n = 8 일 때는?
n = 6 (2를 추가해주는 타일)
n = 4 (4를 추가해주는 타일)
n = 2 (위에서 만든 6을 추가해주는 타일)
한 후에,
8을 추가해 주는 타일 2개를 추가하자.
import sys
N = int(sys.stdin.readline())
dp = [0 for i in range(31)]
dp[2] = 3
for i in range(4, N + 1, 2):
dp[i] = dp[i - 2] * 3
for j in range(i - 4, -1, -2):
dp[i] += dp[j] * 2
dp[i] += 2
print(dp[N])
