백준 #2579 - 계단 오르기

 

DP로 푸는 문제

DP는 메모이제이션이라고 생각하고 풀면 쉽게 풀 수 있다.

이전스텝에서 현재스텝일때 계단의 가치를 메모이제이션 해두면 연산을 여러번 안해도 되기 때문에

수행시간을 줄일 수 있다.

def dp(memo, prev, now, steps):
    if now == 0:  # 시작은 계단으로 안친다.
        return 0
    if steps == 3:  # 연속 세 개 밟을 수 없음
        return 0
    if memo[prev][now]:    # 이미 계산한 것이라면
        #return memo[prev][now]
        pass
    else:
        if now-2 >= 0:
            a = dp(memo, now, now-1, steps+1)
            b = dp(memo, now, now-2, 1)
            memo[prev][now] = stepVal[now-1] + max(a,b)
        else:
            memo[prev][now] = stepVal[now-1] + dp(memo, now, now-1, steps+1)
            
    return memo[prev][now]


N = int(input())
stepVal = [int(input()) for i in range(N)]
memo = [[None for i in range(N+1)] for i in range(N+1)]
res = dp(memo, N, N, 1)
print(res)