백준 2579번 : 계단 오르기

문제 : www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

풀이

엄청 틀린 문제다. 두번 연속이 안된다는 조건 때문에 현재 연속 상황을 변수로 넣고 하며 다이나믹 프로그래밍을 진행했다. 결국 답을 찾아본 문제다.

dp에 계단을 더할때 현재 계단만 더할 생각을 했다.

① i - 2 최대값 + i 계단 /  ② i - 3 최대값 + i - 1 계단 + i 계단  중 더 큰 값을 dp값으로 지정해주면 된다.

처음에는 ③ i - 4 최대값 + i - 2 계단 + i - 1 계단 을 포함한 3가지 경우 중 큰 경우를 선택했다. dp에 입력하는 중 현재 계단을 밟지 않고 가장 큰 값을 가지는 경우를 고려하기 위해서이다. 하지만 이 방법으로 하면 2개의 계단을 뛰어넘는 경우가 생긴다. 그리고 가만보면 ①과 겹친다. 어차피 마지막 계단은 꼭 밟아야 하고 그때 이전 dp들 중 큰 값으로 알아서 고를것이기 때문에 굳이 안밟는 경우는 생각해 줄 필요가 없다.

 

n = int(input())
steps = []
dp=[0 for i in range(n)]
for i in range(n):
    steps.append(int(input()))

dp[0] = steps[0]
if n >= 2:
    dp[1] = steps[0] + steps[1]
if n >= 3:
    dp[2] = max(dp[0] + steps[2], steps[1]+steps[2])
if n >= 4:
    for i in range(3, n):
        dp[i] = max(dp[i-2] + steps[i], dp[i-3] + steps[i-1] + steps[i])
 
 print(dp[n-1])