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

문제링크: www.acmicpc.net/problem/2579

2579번: 계단 오르기

---

문제 설명

- N: 계단의 개수

- N개의 계단의 점수가 주어짐.

조건

1. 계단은 한 번에 한 계단 or 두 계단 오르기 가능

2. 연속된 세계의 계단을 모두 밟아서는 안 된다.

3. 마지막 도착 계단은 반드시 밟아야 함.

 

아래 그림과 같이 마지막 지점에 도착했을 때 해당 조건을 지키며 갈 수 있는 점수의 최댓값을 구하면 됩니다.

---

풀이

DP(다이나믹 프로그래밍) 냄새가 물씬 나는 문제였습니다.

마지막 지점을 무조건 도착해야함과 연속 세 개의 계단을 밟지 못하는 점을 명심해서 생각해보면.....

마지막 지점 = 마지막 점수 + 2가지 경우 중 최대

1. 뒤에서 1번째 계단(점수가 10인 지점) + 뒤에서 3번째 계단(점수가 15인 지점) 까지의 max값

2. 뒤에서 2번째 계단(점수가 25인 지점) 까지의 max값

 

점화식을 세워보면 아래와 같이 나온다.

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

 

그리고 초기화를 할 때 세번째 계단까지 해주는데, 길이가 2이하인 경우는 따로 예외처리로 계산해 주어야 합니다.

 

코드

from sys import stdin
stdin = open("input.txt", "r")
# N: 계단의 개수
N = int(stdin.readline())

stairs = [int(stdin.readline()) for _ in range(N)]

if N <= 2:
    print(sum(stairs))

else:
    DP = []
    DP.append(stairs[0]) # 첫번째 계단
    DP.append(stairs[0] + stairs[1]) # 두번째 계단 까지의 최댓값
    DP.append(max(stairs[2] + stairs[1], stairs[2] + stairs[0])) # 세번째 계단은 1, 2 or 0, 2 두가지 경우로 이루어질 수 있음.

    for i in range(3, N):
        # print(DP)
        DP.append(stairs[i] + max(DP[i-2], stairs[i-1] + DP[i-3]))
    print(DP[-1])