반응형
-풀이
n = int(input())
no, left, right = 1, 0, 0
for i in range(n):
no = no + left + right
left = no - left
right = no - right
print((no + left + right) % 9901)
-풀이설명
[30분 no sol] 오랜만의 DP문제.. 역시나 규칙을 찾기 실패했고 구글링을 하게 되었다. no, left, right는 차례대로, 첫째 줄에 빈 공간, 왼쪽 칸, 오른쪽 칸일 경우의 수를 나타내어 준다. 배열로 나타내지 않은 이유는 no가 항상 가장 크고, left, right는 항상 양수이기 때문이다.
'알고리즘' 카테고리의 다른 글
| [수학] 백준 1024 파이썬 (수열의 합) 실버2 (0) | 2021.12.31 |
|---|---|
| [수학] 백준 1011 파이썬 (Fly me to the Alpha Centauri) 골드5 (0) | 2021.12.30 |
| [브루트포스] 백준 1120 파이썬 (부분수열의 합) 실버2 (0) | 2021.12.28 |
| [브루트포스] 백준 1120 파이썬 (문자열) 실버4 (0) | 2021.12.27 |
| [그래프 탐색] 백준 1012 파이썬 (유기농배추) 실버2 (0) | 2021.12.27 |