Algorithm

[백준] 1309 동물원 Python

YunSeong 2021. 8. 8. 02:15
728x90
반응형

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

 

1309번: 동물원

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

www.acmicpc.net

 

일단 이 문제를 풀기 위해서 N이 각각 1, 2, 3 일 때를 생각해봤다. 

 

N = 1일 때는

   
  사자  
    사자

이렇게 생겼고 

 

N = 2 일 때는

N = 1에서 아무 사자 없는 두 칸을 붙이거나 

사자가 한마리 있는 두 칸을 붙인 듯이 이루어져있다.

 

N = 3

일 때는

N = 2일 때 아무 사자 없는 두 칸을 붙일 때 즉 7개

N = 1일 때 아무 사자 없는 두 칸과 사자가 한 마리가 있는 두 칸을 붙일 때 즉 3 * 2개

N = 2일 때 사자가 제일 위에 한 마리 있을 때 사자 한마리 있는 두 칸을 붙일 때 즉 7 - 3개

를 다 더한 7 * 2 + 3 = 17개이다. 

 

 

여기서

dp[i] = dp[i-2] + dp[i-1] * 2이라는 점화식을 만들 수 있다.

 

1
2
3
4
5
= int(input())
dp=[37]
for i in range(2 , N) :
    dp.append(dp[i-1]*2%9901+dp[i-2]%9901)
print(dp[N-1]%9901)
cs

위에서 구한 점화식을 이용해서 위와 같은 코드를 만들었다.

 

 

 

728x90
반응형

'Algorithm' 카테고리의 다른 글

[백준] 16953 A to B Python, 깊은 복사  (0) 2021.08.02
[백준] 10164 격자상의 경로 Python  (0) 2021.08.02