[www.acmicpc.net/problem/2579]
#풀이
- 동적 계획법
1. 현 계단 위치에서 항상 다음 계단으로 올라갈 수 있는 상태로 만든다.
2. n-1 번째 계단에서 한 칸 올라간 후 와 마지막 계단을 비교하여 최댓값을 출력한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | import sys input = lambda : sys.stdin.readline().rstrip() n=int(input()) stair=[0] for _ in range(n): stair.append(int(input())) #dp를 담을 배열(shallow copy) dp=stair[:] for i in range(0,n-1): if i+2<=n: #현재 위치에서 두칸 올라가기 dp[i+2]=max(dp[i+2],stair[i+2]+dp[i]) if i+3<=n: #현재 위치에서 한칸 올라가고 다시 두칸 올라가기 dp[i+3]=max(dp[i+3],stair[i+3]+stair[i+1]+dp[i]) #max(마지막 계단, n-1번째 계단 에서 한칸 올라가기) print(max(dp[n],stair[n]+dp[n-1])) | cs |
댓글 쓰기