[스파르타] 99클럽 코테스터디 2일차 TIL / 백준 1309

1309번: 동물원 (링크)

1309번: 동물원

 

점화식 규칙을 찾지 못해서 다른 풀이를 참고했다. DP로 작게 쪼개서 생각하면 됨!

n = 1, 2 인 경우에만 초기에 설정해주고 그 다음부터는 그 직전에 추가하면 된다.

 

n = 1

0마리: 1

1마리: 2

총합: 3

 

n = 2

0마리: 1

1마리: 4

2마리: 2

총합: 7

 

n = 3

0마리: 1

1마리: 6

2마리: 8

3마리: 2

총합: 17

 

n = 4

0마리: 1

1마리 8

2마리: 18

3마리: 12

4마리: 2

총합: 41

 

import sys
input = sys.stdin.readline

n = int(input())

dp = [0] * 100001
dp[1], dp[2] = 3, 7

for i in range(3, n+1):
    dp[i] = (dp[i-1] * 2 + dp[i-2]) % 9901

print(dp[n])

 

오늘 미들러 풀이 끝!