[백준]2579번 계단 오르기 - DP

 

n = int(input())

stair = [0 for i in range(301)] # 계단의 최대 수 300 개
point = [0 for i in range(301)] # 계단이 3개 이하일 경우, 인덱스 에러를 방지하기 위해 0으로 초기

for i in range(n):
    stair[i] = int(input())

point[0] = stair[0]
point[1] = stair[0] + stair[1]
point[2] = max(stair[0] + stair[2], stair[1] + stair[2]) # 무조건 3번째 계단을 밟아야 하므로 0,2 와 1,2 중 큰거로 저장

for i in range(3, n):
    # 2칸 올라온 경우 전 계단은 신경 안씀, 1칸만 올라온 경우 연속 3칸 올라오지 못하게 하기 위해
    # 2번째 전의 누적 값 + i-1 번째의 값 + 현재 올라갈 계단의 값
    point[i] = max(point[i - 2] + stair[i], point[i - 3] + stair[i - 1] + stair[i])

print(point[n-1])

 

코드 설명

계단의 값을 저장하기 위한 stair, 누적 값을 저장하기 위한 point 리스트를 300 길이만큼 선언한다. (계단의 최대 수 : 300 이므로)

3번째 계단까지는 주어진 조건을 통해 결정해준다.

그 후 반복문을 통해 point[i - 2] + stair[i] 값과 point[i - 3] + stair[i - 1] + stair[i] 값중 큰 값을 저장하여 누적시킨다.

 

Point : 연속해서 3개의 계단을 밟을 수 없는것이 포인트이다. 따라서 point[2] 의 값도 1, 3 와 2, 3 번째 계단을 밟은 값 중에서 큰 값을 선택하여 저장한다. 

3개 이상의 계단인 경우 2가지의 case 가 존재한다.

case 1 : i-2 + i

case 2 : i-1 + i -> 이 경우 3개의 계단을 연속해서 밟을 가능성이 존재 따라서 식을 수정

-> i-3 번째 까지 밟은 누적 값 + i-1 번째를 밟고 + 현재 i 번째를 밟게 되는 경우로 식을 수정할 수 있다.

위의 2가지 케이스의 점화식을 이용해서 값을 구할수 있다.