https://www.acmicpc.net/problem/1309
1309번: 동물원
첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.
www.acmicpc.net
풀이 과정
d[i][k]를 2xi 우리에 사자를 가두는 경우의 수라고 하자. k = 0, 1, 2는 마지막 i번째 행에 사자가 없거나, 왼쪽에 있거나, 오른쪽에 있는 경우이다.
그러면,
d[i][0] = d[i-1][0] + d[i-1][1] + d[i-1][2]
d[i][1] = d[i-1][0] + d[i-1][2]
d[i][2] = d[i-1][0] + d[i-1][1]
의 점화식이 성립한다
소스 코드
"""
가로 세로 인접 x, 몇가지?
0, 1, 2 안두기 왼쪽 오른쪽, 9901은 나머지 처리 잘하기
"""
import sys
N = int(sys.stdin.readline())
mod = 9901
d = [[0, 0, 0], [1, 1, 1]]
for i in range(2, N+1):
d.append([(d[i-1][0] + d[i-1][1] + d[i-1][2]) % mod, (d[i-1][0] + d[i-1][2]) % mod, (d[i-1][0] + d[i-1][1]) % mod])
print(sum(d[N]) % mod)'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글
| 백준 2156 - 포도주 시식 [파이썬] (0) | 2022.04.30 |
|---|---|
| 백준 11057 - 오르막 수 [파이썬] (0) | 2022.04.22 |
| 백준 1149 - RGB 거리 (0) | 2022.04.22 |
| 백준 15988 - 1, 2, 3 더하기 3 [파이썬] (0) | 2022.04.21 |
| 백준 1699 - 제곱수의 합 [파이썬] (0) | 2022.04.21 |