이 문제는 앞의 네트워크 선 자르기 문제와 동일해 보이나 다른 점은 마지막에 땅까지 도착하는 지점이 하나 추가된다는 것이다
|
1
2
3
4
5
6
7
8
9
10
|
if __name__=='__main__':
n = int(input())
arr = [0] * (n+2)
arr[1] = 1
arr[2] = 2
for i in range(3, n+2):
arr[i] = arr[i-1] + arr[i-2]
print(arr[n+1])
|
cs |
이러한 유형의 문제는 중간 징검다리는 건널 수 없는 조건이 생긴다던지 다른 방법으로 응용되서 나올 수 있다
728x90
'Data Structures & Algorithms' 카테고리의 다른 글
| [Algorithms] 동적 계획법(Dynamic Programming)-가장 높은 탑 쌓기 (LIS 응용) (0) | 2022.06.07 |
|---|---|
| [Algorithms] 동적 계획법(Dynamic Programming)-최대 부분 증가수열 (0) | 2022.06.07 |
| [Algorithms] 완전탐색(백트랙킹, 상태트리와 CUT EDGE)/깊이우선탐색(DFS) Basic-피자 배달 거리(DFS 활용) (0) | 2022.06.06 |
| [Algorithms] 깊이/넓이 우선 탐색 (DFS, BFS) 활용-사다리 타기(DFS, BFS 2가지 방법으로) (0) | 2022.06.05 |
| [Algorithms] 깊이/넓이 우선 탐색 (DFS, BFS) 활용-토마토 (BFS 활용) (0) | 2022.06.05 |