[백준 1309] 동물원

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

1309번: 동물원

---

접근

N이 1부터 3일 때 경우의 수를 먼저 구하였다.

각각의 크기에서 사자를 0마리, 1마리, 2마리 등을 놓을 수 있을 때로 나누어 계산을 하였다. 그 결과는 다음과 같다.

• N=1 -> 1 + 2 = 3
• N=2 -> 1 + 4 + 2 = 7
• N=3 -> 1 + 6 + 8 + 2 = 17
• N=4 -> 41

여기서 규칙을 구할 수 있었다. 현재 N이 i일 때의 경우의 수를 구할 때 i-1번째 경우의 수 x 2 + i-2번째 경우의 수를 하면 i번째의 경우의 수가 나왔다.

 

구현

- 먼저 N이 1일 때와 2일 때의 경우의 수를 저장하였다.

- N이 3 이상일 때는 위에서 구한 식대로 해당 차례의 경우의 수를 구하였다.

- 이때 수가 커질수록 경우의 수가 매우 커지기 때문에 계속해서 9901로 나눈 나머지를 저장하였다.

- 이를 통해 최종적으로 dp[N]의 값을 출력하였다.

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