백준 2579번 - 계단 오르기

 

계단을 오르면서 밟는 발판의 최댓값을 구하는 문제다. 이전에 풀었던 삼각형 문제나 집 색깔 문제처럼 뒤에서 차례대로 더하면서 갱신해주는 방식을 생각했지만, 경우가 깔끔하게 나뉘는 것도 아니었고 규칙이 있는 것도 아니었다. 꼭 나눠줘야 하는 경우는 i번째 발판(s[i-1])을 밟기 전에 바로 전 발판(s[i-2])을 밟았는지 전전 발판(s[i-3])을 밟았는지 경우를 나누어 주고, 바로 전 발판(s[i-2])을 밟았다면 그 바로 전 발판(s[i-3])은 밟지 못하기 때문에, 전전 발판(s[i-4])까지 밟기까지의 경우의 최댓값(dp[i-3])에 s[i-1] 값과 s[i]값을 더해준 경우와 전전 발판(s[i-3])을 밟은 경우의 최대값을 비교해서 큰 값을 dp에 append 해주면 i번째 발판까지의 최대값이 구해지기 때문에, 답을 구할 수 있다.

 

##함수 선언 부분##
import sys
##변수 선언 부분##
s = []
dp = []
##메인 함수 부분##
if __name__ == "__main__":
    N = int(input())
    for i in range(N):
        s.append(int(input()))
    dp.append(s[0]) #N=1인 경우
    if N == 1:
        print(dp.pop())
        sys.exit(0)
    dp.append(s[0]+s[1]) #N=2인 경우
    if N == 2:
        print(dp.pop())
        sys.exit(0)
    dp.append(max(s[0]+s[2], s[1]+s[2])) #N=3인 경우
    for i in range(3,N): #N>3인 경우
        dp.append(max(dp[i-3] + s[i-1] + s[i], dp[i-2] + s[i]))
    #마지막 발판을 밟아야하기 때문에, 바로 그 전 발판을 밟은 경우의 최댓값과, 전전 발판을 밟은 경우의 최댓값 중
    #큰 값을 비교해야 된다.
    print(dp.pop())

규칙도 안보이고 경우를 나눌 때도 기준이 없어서 어려웠다. 조건이 주어질 때 어떤 식으로 경우를 나누어 줘야할 지 생각을 많이 해보는 것이 중요할 것 같다.