[DP/백준]2579

1256 단어 백준DPDP

백준 2579 번 문제

def solution(n, stair_array):

    count_array = [0 for _ in range(n)]

    if n == 1:
        return stair_array[0]
    
    if n == 2:
        return stair_array[0] + stair_array[1]

    count_array[0] = stair_array[0]
    count_array[1] = stair_array[0] + stair_array[1]
    count_array[2] = max((stair_array[0] + stair_array[2]), (stair_array[1] + stair_array[2]))

    for i, _ in enumerate(count_array):
        if i == 0 or i==1 or i==2:
            continue
        count_array[i] = max((count_array[i-3] + stair_array[i-1] + stair_array[i]), (count_array[i-2] + stair_array[i]))
    
    return count_array[n-1]

n = int(input())
stair_array = []

for i in range(n):
    stair_array.append(int(input()))

print(solution(n, stair_array))
  • n은 자연수이므로 n = 1, n = 2일때만 예외처리를 해주었다(예외처리 안하면 outofindex 남)
  • 현재 계단의 최댓값은
    (세번째 전의 계단까지의 최댓값 + 바로 이전의 계단 값)
    vs
    (두번째 전의 계단까지의 최댓값)
    중 선택하도록 한다
  • 그래야 한계단씩 두번 오르는 경우를 막을 수 있다(일단 처음에 무조건 두계단을 오르는 것을 비교함)

사실 4트이지만 코드 깔짝거리면서 바꾼 수준이라 따로 안적었다

좋은 웹페이지 즐겨찾기