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

문제

백준 2579번 계단 오르기 문제를 해결했습니다.

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

2579번: 계단 오르기

문제와 그림이 함께 있기 때문에, 가독성을 위해 문제 내용은 생략하도록 하겠습니다. 링크를 참고해주세요!

 

문제 풀이

해당 문제는 세 가지 조건이 있는 문제입니다.

• 한 번에 한 계단 혹은 두 계단씩 오를 수 있다.
• 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.
• 마지막 도착 계단은 반드시 밟아야 한다.

해당 규칙을 지키면서 계단에 매겨진 점수가 최대값이 되도록 계단을 오르는 문제입니다. 처음엔 무작정 규칙을 찾아서 해결해보려고 시도했습니다. 한 칸 올랐을 때와 두 칸 올랐을 때 못밟는 계단이 발생하기 때문에, 못밟는 계단의 값을 비교해서 오르면 어떨까? 하는 생각이 들었습니다. 하지만, 경우의 수가 많아서 규칙을 모두 지키면 조건문도 많아지고 모든 경우를 커버할 수 있을 것이라는 확신이 없었습니다.

 

따라서, 알고리즘을 활용하기로 했습니다. 이번 문제는 계단의 값을 쌓아 최대값을 만드는 문제이기 때문에, DP(Dynamic Programming)으로 푸는 것이 좋겠다고 판단했습니다. DP에 저장할 값은 DP[i]번째까지 왔을 때 점수의 최대값입니다. 계단의 점수가 stair 리스트에 저장되어 있다고 가정하고, 점화식을 만들기 위해 예시를 확인해보겠습니다.

 

1. 첫 번째 계단

DP[0] = stair[0]

 

2. 두 번째 계단

DP[1] = stair[0] + stair[1]

 

3. 세 번째 계단

DP[2] = stair[1] + stair[2] 혹은 stair[0] + stair[2]

 

둘 중 큰 값을 고릅니다.

 

4. 네 번째 계단

DP[4] = stair[0] + stair[1] + stair[3] + stair[4] 혹은 stair[0] + stair[2] + stair[4]

 

네 번째 계단을 보면, 겹치는 값들이 보입니다. 해당 값을 DP를 활용해서 변경해보겠습니다.

DP[4] = DP[1]+stair[3]+stair[4] 혹은 DP[2]+stair[4] 

위에 두 개의 식 중에 더 큰 값을 DP에 저장하게 됩니다. 이를 점화식으로 나타내면 다음과 같습니다.

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

 

위 식을 활용해 N번째 계단(도착점)까지 오는 최대 점수를 알 수 있습니다.

코드로 표현하면 다음과 같습니다.

N = int(input())
stair = [0]*301
for i in range(N):
    stair[i]=int(input())

DP = [0]*301
DP[0] = stair[0]
DP[1] = stair[0]+stair[1]
DP[2] = max(stair[0]+stair[2], stair[1]+stair[2])

for i in range(3, N):
    DP[i] = max(DP[i-3] + stair[i-1] + stair[i], DP[i-2]+stair[i])

print(DP[N-1])

정리

DP는 결과값을 얻기 위한 과정을 쌓아가는 것입니다. 이전 결과 값을 활용해 N번째에서 최선의 값을 얻을 수 있습니다.