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

안녕하세요. 매일 공부하는 개발자 빅광스입니다.

제가 아직 다이나믹프로그래밍이 익숙치 않아서 오늘도 또한 다이나믹 프로그래밍 문제를 풀도록 하겠습니다.

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

2579번: 계단 오르기

계단오르기 문제인데요, 자세한 내용은 링크를 타고 들어가서 문제를 확인 해보시기 바랍니다.

 

우리는 이 문제를 해결하기위하여 Sub Problem을 정의하고 메모리제이션 기법을 활용하여 이전에 올라왔던 계단위치의 합을 활용하여

시간 복잡도를 줄일 것 입니다.

 

 우리는 n번째 계단을 오르기위해서는 n-2 번째 계단에서 계단을 2단계 오르는 방법과 n-1번 계단에서 계단을 1단계 오르는 방법 2가지로 나눌 수 있습니다. 우리는 최대값을 구해야 하기 때문에 max( subproblem(n-2) + 현재계단(n), subproblem(n-1) + 현재계단(n) ) 으로 계산 할 수 있습니다.

 

그러나 해당 조건을 만족시켜야합니다 : 연속된 계단 3개는 오를 수 없다.

따라서 subproblem(n-1)을 사용 할 수 없습니다. subproblem(n-1)으로 계산하게 된다면 연속된 계단을 3개 오를 수 있기 때문 입니다.

즉 subproblem(n-1) 대신하여 subproblem(n-3) + 현재계단(n) + 현재계단(n-1) 로 계산을 할 수 있습니다.

 

결론은 subproblem(n-1)로 계산하게된다면 연속된 3개가 포함 되기 때문에 우리는 subproblem(n-3) + 현재계단(n) + 현재계단(n-1) 로 계산 하여야 합니다.

 

이 코드를 파이썬 코드로 정리를 해보겠습니다.

stare : 계단의 정보를 가지고 있는 리스트

dp : 각 계단까지의 합의 최대값

N = int(input())
stare = [0 for _ in range(N+1)]
dp = [[] for _ in range(N+1)]
for i in range(1, N+1):
    stare[i] = int(input())

if N >= 3:
    dp[1] = stare[1]
    dp[2] = stare[1] + stare[2]
    dp[3] = max(stare[1]+stare[3], stare[2]+stare[3])
    
    for i in range(4, N+1):
        dp[i] = max(dp[i-2]+stare[i], dp[i-3]+stare[i]+stare[i-1])
        
    print(dp[N])
else:
    print(sum(stare))