공부 자료/알고리즘
(Python/파이썬) 백준 1309번 - 동물원
뚜루뚜루세니
2021. 9. 24. 19:18
728x90
1. 문제출처: https://www.acmicpc.net/problem/1309
1309번: 동물원
첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.
www.acmicpc.net
2. 해결과정:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
N = int(input())
zoo = [1 for _ in range(N+1)] #초기화
zoo[1] = 3
if N == 1:
print(zoo[1])
else:
for i in range(2, N+1):
zoo[i] = (2*zoo[i-1])+zoo[i-2]
zoo[i]%= 9901
#규칙을 찾으면
# zoo[0]=1 하나도 배치하지 않는 경우
# zoo[1]=3 하나도 배치하지 않은 경우 + 왼쪽만 + 오른쪽만
# zoo[2]=7 zoo[3]=17 zoo[4]=41이다.
print(zoo[N])
|
cs |
문제에서 사자 하나도 배치하지 않는 경우도 경우의 수로 하나 카운트 해준다고 했기 때문에 zoo[0] = 1로 설정을 해준다. N이 1,2,3인 경우까지 세 보았더니 규칙이 2*zoo[i-1]+zoo[i-2]로 나왔기 때문에 이를 이용해서 점화식을 세우고 코드를 작성해주면 된다.
3. 느낀점
오랜만에 dp문제! 생각보다 쉬웠던 문제였다.
728x90