[백준 2579번] 계단 오르기 - 동적 계획법

 

# 뭔가 복잡해보이는 문제들도 생각보다 동적 계획법 식으로 생각하면 쉽게 풀리는 경우가 많다!

# 동적계획법으로 풀까?를 결정하는데까지의 시간을 줄이는 걸 목표로!

# 점화식을 생각하는 법을 더 정교하고 빠르게 !

 

-- 정답 코드

 

# 계단 오르기 게임
# 계단을 밟으면 그 계단에 쓰여있는 점수를 얻게된다.

# 계단은 한번에 한 계단 or 두 계단씩, 연속된 3개의 계단을 모두 밟으면 안됨, 마지막 계단은 반드시 밟아야됨
import sys

n = int(input()) # 전체 계단의 개수

stairs = [0] * (n+1) # 시작점을 포함한 계단

for i in range(1, n+1): # 계단의 점수를 stairs에 기록
    stairs[i] = int(sys.stdin.readline().strip())

dp = [0] * (n+1) # 해당층까지 올랐을 때 최고 점수를 기록

# 마지막 층은 꼭 밟아야 하기 때문에 조건이 2가지 있다.
# 1,2,3,4,5,6,7,8,9,10이 있을 때 8,10으로 가는 방법 7,9,10으로 가는 방법
# 따라서 dp[i-2] + stairs[i] 와 dp[i-3] + stairs[i-1] + stairs[i]를 비교하면 되겠다!
for i in range(1,n+1):
    if i==1: # 처음은 무조건 계단 1개
        dp[i] = stairs[i]
    elif i==2: # 계단이 2개면 둘다 밟는게 최대값
        dp[i] = dp[i-1] + stairs[i]
    elif i==3: # 계단이 3개면 1,3 or 2,3 중 최대값
        dp[i] = max(stairs[i-2],stairs[i-1]) + stairs[i]
    else:
        dp[i] = max(dp[i-2] + stairs[i],dp[i-3] + stairs[i-1] + stairs[i])

print(dp[-1])

점화식을 생각하는데 까지 시간이 오래걸렸다. ( 마지막 계단을 꼭 밟아야 한다는 사실을 중요하게 생각하지 못해서 )

처음 1,2 이런식으로 가는데 있어 124와 134를 선택하는데 max를 찾아야 하나?라는 생각을 위주로 처음에 고민했던것 같다. 그러다가 마지막 계단을 밟아야 한다는 조건을 다시 읽게 되었고 그렇다면 마지막 계단을 n이라고 할 때 n-1을 밟거나 n-2를 밟아야 하고, n-1을 밟을 경우에는 n-3, n-2를 밟을 경우에는 그때까지의 최대값을 구하면 되겠다!는 생각을 하게 되었다.

 

여기까지 생각이 드니 아.. 동적계획법..! 이 생각났던것 같다. 이번에는 동적계획법 문제를 풀려고 찾은 문제가 아니었는데도 연달아서 동적계획법 문제를 풀게 되었다. 따라서 점화식을 생각하고 dp 배열을 새로 만들어준 후 i-3까지가 필요하기 때문에 i가 3일때까지는 수동으로 배열을 만들어 주었다. 

 

코드 자체는 어렵지 않으나 DP문제는 확실히 그 아이디어를 찾아내고, 점화식을 만들어 내는게 관건인 것 같다~!!

 

 

 

오늘도 성공적으로 계단을 올라갔다!!