[BOJ/백준] 1309 동물원

# 1309 동물원
# 9901로 나눈 수 출력

N = int(input())
mod = 9901
dp = [0]*(N+1)
if N == 1:
    print(3)
else:
    dp = [1,3]
    for i in range(2,N+1):
        current = 2*dp[-1]+dp[-2]
        dp[-2] = dp[-1]
        dp[-1] = current
    print(current%mod)

직접 그려봐서 점화식을 찾았다.

 

생각해보면 N-1일때, N-1의 위치에 왼쪽에 사자가 있을때, 오른쪽에 사자가 있을때와 둘다 없을때가 있을 것이다.

 

 

 

 

파란색 음영이 있는 곳이 사자가 있다고 한다고 가정하면, N-1 번 위치에 사자가 있을때에는 2가지의 경우의 수가 있다. 그리고 N-1에 사자가 없을때에는 총 3가지가 있다. 그 중에서 둘다 사자가 없는 경우는 N-2의 크기에서 사자를 놔두는 경우의 수가 같은 것이다.

 

점화식을 구하면,

 

F(N) = F(N-1)*2 +F(N-1) 로 나타낼 수 있다.

 

이렇게 구하고, 전체를 구해서 9901로 나눠도 되지만, 그냥 하면, 숫자가 워낙 커지므로 9901로 나눈 나머지로 계산하는 것이 더 빨리 결과가 나온다.

N = int(input())

prev = 1
result = 3
mod = 9901
for _ in range(N-1):
    temp = result
    result = (result*2 + prev)%mod
    prev = temp
print(result)