[백준] 2579 파이썬(python) : 계단 오르기

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

 

import sys
n = int(sys.stdin.readline())
arr = [0]*(301) #1
dp = [0]*(301)
for i in range(n):
    arr[i] = int(sys.stdin.readline()) #2
dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(arr[1]+arr[2], arr[0]+arr[2]) #3
for i in range(3, n): #4
    dp[i] = max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]) #5
print(dp[n-1]) #6

 

#1 : 최댓값 +1로 입력받는 배열과 dp배열을 초기화한다.

#2 : #1에서 리스트 생성으로 초기화 해줘서 입력값을 이렇게 받아야한다(자기자신은 포함해야 해서 arr[2]는 포함시킨다)

#3 : 점화식을 고려했을때 dp를 3개까지는 초기화해줘야 함

#4 : 4번째 요소인 인덱스 3부터 시작해서 마지막 인덱스인 n-1까지 반복(dp테이블을 인덱스 0부터 시작했기 때문)

#5 : 연속된 세수를 받을 수는 없고 최댓값을 만족해야 하니까 i-1을 건너뛴 dp[i-2]+arr[i]과 i-2를 건너뛴 dp[i-3]+arr[i-1]+arr[i]

#6 : 마지막 도착 계단인 dp[n-1]을 출력한다.(dp테이블을 인덱스 0번부터 시작했기 때문에 마지막 인덱스는 n-1이다.)

 

#1이 이해가 안되서 계속 인덱스에러가 떳다. [0]*n 또는 [0]*(n+1)로 초기화한 후 제출하면 인덱스에러가 뜬다. 

 

import sys
n = int(sys.stdin.readline())
step = [ int(sys.stdin.readline()) for _ in range(n) ] + [0]*2
dp = [0]*301
dp[0] = step[0]
dp[1] = step[0] + step[1]
dp[2] = max(step[1]+step[2], step[0]+step[2])
for i in range(3, n):
    dp[i] = max(step[i]+dp[i-2], step[i]+step[i-1]+dp[i-3])
print(dp[n-1])

 

이건 또 맞았다. 왜인지 모르겠다. [0]*1이면 인덱스에러가 나오는데 말이다

---

2156번 : 포도주 시식