[백준] 2579번 계단 오르기(다이나믹 프로그래밍)(DP)(Python - 파이썬)

백준 2579번 문제입니다. (solved.ac)기준 실버 3 문제입니다.

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

2579번: 계단 오르기

문제 접근

첫째 줄에 계단의 개수가 주어지고 둘째 줄 부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여있는 점수가 주어집니다.  계단 오르기 게임에서 얻을 수 있는 최대 점수를 출력하면 됩니다.

 게단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임입니다. 

계단을 오르는데에는 3가지 규칙이 있습니다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

다이나믹  프로그래밍으로 접근하였습니다.

현재값에 최대 점수를 저장할 것 입니다. ex) d[5]는 5번째 계단을 밟았을 때 기준 가장 높은 점수의 합계가 저장.

마지막 계단은 반드시 밟아야 하므로 i번째 계단을 밟았을 때 점수의 최댓값(d[i])은 다음과 같이 구할 수 있습니다.

d[i] = max(d[i-3] + stairs[i-1], d[i-2]) + stairs[i]

 마지막 계단은 반드시 밟아야 하므로 마지막에 stairs[i]는 무조건 더해줍니다.

1, 2 번 규칙을 고려하여 마지막 계단을 밟을 수 있는 두가지 경우중 최댓값을 더하여 줍니다.

첫번째 방법은 3칸전 계단을 밟고(d[i-3] = 3칸전 계단을 밟았을 때 얻을 수 있는 최대 점수) 바로 전 계단을 밟는 방법(stairs[i-1])입니다. 그 후 마지막 계단을 밟아(stair[i]) 줍니다.

두번째 방법은 두칸전 계단을 밟는 것(d[i-2] = 2칸전 계단을 밟았을 때 얻을 수 있는 최대 점수) 입니다.

그 후 마찬가지로 마지막 계단을 밟아(stair[i]) 줍니다.

 d[i-3]을 인덱스 에러없이 계산하기 위해서는 최소 d[1], d[2], d[3]은 미리 하드코딩으로 최댓값을 정하여줍니다.

그 후 4번째 계단부터는 다이나믹 프로그래밍을 이용하여 차근차근 구하면 되는 문제입니다.

정답 코드

n = int(input())

d = [0] * (n+1)
stairs = [0] * (n + 1)

for i in range(1, n + 1):
    stairs[i] = int(input())

d[1] = stairs[1]

if n >= 2 :
    d[2] = stairs[1] + stairs[2]

if n >= 3:
    d[3] = max(stairs[2]+stairs[3],stairs[1]+stairs[3])

for i in range(4, n + 1):
    d[i] = stairs[i] + max(d[i-3] + stairs[i-1], d[i-2])

print(d[n])