[BOJ] 2579. 계단 오르기

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

2579번: 계단 오르기

 

 

1. 해결방법

"""
1. 아이디어
- 첫 번째 계단의 값을 초기 값을 result에 append
- 두 번째와 첫번째의 합, 두 번째를 비교해서 큰 값을 result에 append
- 세 번째는 첫 번째와 세 번째 합, 두 번째와 세 번째의 합을 비교해서 큰 값을 result에 append
- 3번째 부터 n번째 까지 for문을 돌린다.
- 네 번째는 네 번째 인덱스와 result[i-2]의 합과 네 번째 인덱스와 세 번째 인덱스, result[i-3]의 합을 비교해서 큰 값을 result에 append
- 네 번째 인덱스부터는 앞의 인덱스를 더한 값을 가정해야하기 때문에 result의 인덱스를 활용해서 max 연산자로 비교함.
- n이 1 or 2일 때는 for문을 돌렸을 때 런타임에러가 뜨기 때문에 예외 처리

2. 시간복잡도
- O(N)
"""

 

 

2. 정답코드

import sys
input = sys.stdin.readline

n = int(input())
nums = list(int(input()) for _ in range(n))

add_v = 0
result = []

if n >= 3:
    result.append(nums[0])
    result.append(nums[1] + nums[0])
    result.append(max((nums[2] + nums[1]), (nums[2] + nums[0])))

    for i in range(3, n):
        # 3번째 조건
        if i == n:
            result.append(result[i - 1] + nums[i])
        # 1, 2번째 조건
        else:
            result.append(max(nums[i] + result[i - 2], nums[i] + nums[i - 1] + result[i - 3]))

    print(result.pop())

elif n == 2:
    print(max(nums[1] + nums[0], nums[1]))
elif n == 1:
    print(nums[0])

DP문제이며 본인은 개인적으로 어려웠다.
생각을 꽤 깊이 한 문제이며, 특히나 계단의 합을 result로 append 하는것에서 많이 막힌 것 같다.