1309번 동물원(python3)

https://www.acmicpc.net/problem/1309

1309번: 동물원

dp를 적용해주면 된다.

처음에는 dp테이블을 하나만 설정해서 해결하는 방법을 찾았지만 해결하지 못했다. 그래서 dp테이블을 세개로 나누어서 문제를 풀었다.

 

N = int(input())

no_data = [0] * 100001
left_data = [0] * 100001
right_data = [0] * 100001
no_data[0] = 1

for i in range(1, N + 1):
    no_data[i] = left_data[i - 1] + right_data[i - 1] + no_data[i - 1]
    left_data[i] = right_data[i - 1] + no_data[i - 1]
    right_data[i] = left_data[i - 1] + no_data[i - 1]

print(no_data[N] + left_data[N] + right_data[N])