[백준, 파이썬] 2579번 계단 오르기

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

2579번: 계단 오르기

이 문제는 DP에서 상당히 유명한 문제입니다. 

solved.ac 에서 책정한 기준으로는 실버 3정도의 난이도이지만.. 제 기준에선 그것보다는 어려웠던것 같습니다. 

여기서는 문제를 풀기위한 점화식을 세우는 것이 까다롭습니다. 

 

우선 문제의 조건은 아래와 같습니다. 

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

위 세가지 조건이 점화식을 세우는 조건입니다.

위 기준에 따라서 처음에 점화식은 쉽게 새울 수 있었습니다.

dp[i]가 'i번째 계단까지 올라오는데 얻을 수 있는 최고의 점수' 라 세우고 점화식을 세우면 아래와 같습니다. 

dp[i] = max( i번째 계단의 값 + i-1번째 계단의 값 + dp[i-3], i번째 계단의 값 + dp[i-2])

위 점화식이 세워진 이유는 아래와 같습니다. 

이와 같이 dp[4], 즉 4번째 계단까지 올라오는데 얻을 수 있는 최고의 점수를 구해봅시다

 

먼저 1번의 경우를 보겠습니다.

이 경우는 우선 4번째 계단과 3번째 계단의 값을 더합니다. 그렇게 되면 현재 3,4번째 계단이 연속으로 밟혀져 있는 상태가 되므로, 만약 2번째 계단을 밟는 어떠한 경우라도 여기에 포함되게 된다면, 문제의 조건을 위배하게 됩니다. 

따라서 이 경우를 배제하고자, 여기에 dp[i-3]인 dp[1], 즉 1번 계단까지 올라오는데 얻을 수 있는 최고의 값을 더해주는 것입니다. 이렇게 된다면 2번째 계단을 밟는 경우를 배제하고 값을 구한것이므로 문제의 조건을 위배하지 않은 경우의 수를 구할 수 있게 됩니다. 

 

다음 2번째 경우 입니다. 

이 경우는 4번째 계단을 밟고, 아예 처음부터 연속으로 계단을 밟을 여지를 남기지 않는 경우 입니다. 

즉 dp[i-2] = dp[2] (두번째 계단까지 얻을 수 있는 최고의 값) 에 4번째 계단의 값을 더해준다면 연속으로 계단을 밟는 경우를 모두 배제한 것이므로 조건의 만족하는 경우의 수를 구할 수 있게 됩니다. 

 

따라서 이 1번과 2번의 값을 계산하고 그 중 큰 값을 비교한다면 , dp[i]의 값을 구할 수 있게 될것입니다.

 

하지만 주의해야할 점은, i값이 너무 작아 위 점화식의 인덱스를 포함하지 못하는 경우들 ,

즉 dp[0],dp[1],dp[2]에 대해서는 따로 점화식을 구하여 값을 입력해 주어야 합니다.. 

이 값은 dp[0] == 0 , dp[1] == 첫번째 계단의 값 , 그리고 dp[2] = max(1번,2번계단의 합, 1번 계단의 값) 

으로 설정할 수 있습니다.

 

따라서 위 알고리즘을 토대로 코드를 구현하면 다음과 같습니다.

 

 

n = int(input()) stair = [int(input()) for _ in range(n)] dp = [0 for _ in range(n+1)] def solve(): for i in range(n+1): if i == 0: continue elif i ==1: dp[i] = stair[i-1] elif i ==2: dp[i]= max(stair[i-1]+stair[i-2], dp[i-1]) else: dp[i] = max(stair[i-1]+stair[i-2]+dp[i-3],stair[i-1]+dp[i-2]) print(dp[-1]) solve()