[python3] 2579번: 계단 오르기

풀이 일자: 23.02.16

난이도: [Silver 3]

분류: [DP]

 

문제 내용

 

 

문제 해결 흐름

1. 대표적인 DP문제로 점화식을 뽑아내는 것이 가장 중요하다.

→ 해당 문제에서 가장 중요한 제약 조건은 시작점을 계단으로 치지 않고 세 계단 연속으로 밟을 수 없다는 것이었다.

→ 3번째 계단까지는 시작점을 계단으로 계산하지 않는다는 점에서 따로 계산했고 그 이후부터는 점화식을 사용했다.

dp[i-2] => 2칸으로 현재 위치로 올라왔을 때 값 dp[i-3] + stair[i-1] => 1칸으로 현재 위치로 올라왔을 때 값

 

 

ex. 왜 dp[i-1]로 안했는지에 대한 의문이 든다면?

만약 dp[i-1]이라고 하자.. dp[i-1]은 현재 위치보다 1보다 낮은 계단에 도착했을 때의 최대값이다.

그런데 dp[i-1]에는 이전에 1칸으로 올라온 값이 포함되어있어 전체적으로 3칸을 연속으로 올라가지 말라는 제약사항에 위배되므로 dp[i-3]에서 2칸 올라와서 stair[i-1]의 값이 포함되는 값이 올라올 때의 최대값이다.

 

n = int(input());
stair = list();
dp = [0 for i in range(n)];

for i in range(n):
    stair.append(int(input()));
    
for i in range(n):
    if i <= 1:
        dp[i] = sum(stair[:i+1]);
    elif i == 2:
        dp[i] = stair[i] + max(stair[0], stair[1]);
    else:
        dp[i] = stair[i] + max(dp[i-2], dp[i-3] + stair[i-1])

print(dp[n-1]);

 

 

다른 해결 방식

간단한 문제이기도 하고 DP를 쓰라고 노골적으로 나온 문제이기에 모두 같은 방식으로 풀었다.

 

 

문제 링크

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

2579번: 계단 오르기