계단 오르기 - 2579번

점화식을 이용해야하는 다이나믹프로그래밍 문제이다.

그리디처럼 보이는 최대값, 최소값 등을 찾는데 동적 프로그래밍(다이나믹프로그래밍을 이렇게 부르기도 한다)을 사용하기도 한다.

 

문제에 제시된 규칙을 지키며 최대값을 구해야 한다.

첫번째 계단부터 하나씩 올라가면서 각 계단에서의 최대값을 구해보도록 나눠서 생각했다.

이문제에서 특히 고려해야할 점은 3계단을 연속으로 올라갈 수 없는 규칙이다.

 

변수('cant_go')를 하나 만들어서 계단을 올라가면 1을 더해주고 연속된 계단을 올라갈때 누적으로 1을 계속 더해준다.

변수의 값이 3이 됬을 때 계단을 3칸 연속으로 오른 경우가 되므로 한칸밑에 있는 계단을 스킵할 지, 2칸 밑에있는 계단을 스킵할지 정해줘야한다.

각 경우의 점수중 큰수를 해당 계단에서의 획득할 수 있는 최고점수로 책정하고, 경우별로 변수의 값을 1 또는 2로 바꿔준다. (한칸 밑 계단을 스킵했으면 변수의 값을 1로, 2칸 밑 계단을 스킵했으면 변수의 값을 2로)

 

도움되는 반례로는 아래 반례가 있다.

5
1
4
3
1
9

 

 

n = int(input())
st = [0]
l = [0]*(n+1)
for _ in range(n):
  st.append(int(input()))

cant_go = 0
for i in range(1,n+1):
  
  # 한칸 밑의 계단에서의 점수를 사용하는 방법과,
  # 2칸 밑의 계단에서의 점수를 사용하는 방법중 큰수를 사용
  l[i] = max(l[i-1]+st[i], l[i-2]+st[i])
  if l[i-2]+st[i]>=l[i-1]+st[i]:
    cant_go = 1
  else:
    cant_go+=1
  if cant_go == 3:
    l[i] = max(l[i-2]+st[i], l[i-3]+st[i-1]+st[i])
    if l[i-2]+st[i]>=l[i-3]+st[i-1]+st[i]:
      cant_go = 1
    else:
      cant_go = 2
print(l[n])