[백준 - Python] 2579번 : 계단 오르기

 

 

🌱   문제

 

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

2579번: 계단 오르기

 

💡   설명

필자는 해당 문제를 BFS로 해결하려 했으나 채점 7% 에서 메모리 초과가 발생하였습니다.

아무리 n이 300이라고 해도 주어진 메모리가 128MB인 상황에서 메모리를 많이 요구하는 BFS로 문제를 해결하기에는 문제가 있어 보였습니다.

다음 방법으로 다이나믹 프로그래밍(DP)로 접근을 시도하였습니다.

Memoization 기법을 통해 이전에 구한 최적값(해당 층까지 구한 최대 스코어)을 dp 배열에 기록해두고 한 층씩 높여가며 해결하였습니다.

 

우선 점화식을 세워주기 위해 문제에서 제시하는 조건을 살펴보겠습니다.

1. 계단은 한 번에 한 층 또는 두 층 이동 할 수 있습니다.
2. 층을 세 번 연속하여 이동할 수 없습니다. (4층 -> 5층 -> 6층 이동과 같은 움직임이 불가능하다는 의미.)
3. 도착하고자 하는 층을 밟아야만 합니다.

 

'연속으로 3개의 층을 거치지 않고 이동할 수 있는 2가지 방법'

 

해당 조건을 그림으로 도식화 해보면 크게 파란색 경로와 초록색 경로 2가지로 표현할 수 있습니다.

이렇게 설계하면 조건을 만족하면서 모든 층을 확인해보며 결과를 도출해낼 수 있습니다.

• 파란색 경로는 3개의 층을 연속해서 거치지 않기 위해 애초에 2칸씩 이동하는 경우
• 초록색 경로는 3개의 층을 연속해서 거치지 않기 위해 두칸 이동하고 한 칸 이동하는 경우

 

점화식은 아래와 같습니다.

• DP[i] = max(arr[i] + dp[i-2], arr[i] + arr[i-1] + dp[i-3])

 

풀이를 위해서 우선 Base가 되는 1층, 2층, 3층에 대한 최대 값을 구해주어야 합니다.

그리고 4층부터 n층까지 위 점화식을 반복하면 결과를 도출해낼 수 있습니다.

 

✏️   소스코드

n = int(input())

arr = [0] + [int(input()) for _ in range(n)]
dp = [0] * (n+1)

if n == 1: print(arr[1])
elif n == 2: print(arr[1] + arr[2])
else: 
    dp[1] = arr[1]
    dp[2] = arr[1] + arr[2]
    dp[3] = max(arr[1] + arr[3], arr[2] + arr[3])

    # 계속 2칸씩 or 1칸 + 2칸 반복
    for i in range(4, n+1):
        dp[i] = max(arr[i] + dp[i-2], arr[i] + arr[i-1] + dp[i-3])

    print(dp[n])

 

 

 

github : https://github.com/tmdgh1592

tmdgh1592 - Overview