[2579] 계단 오르기

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

import sys
n = int(sys.stdin.readline().strip())

l = []
for _ in range(n):
    l.append(int(sys.stdin.readline().strip()))

l_max = [0 for _ in range(n)]
# 0
l_max[0] = l[0] 
# 01
if n >= 2:
    l_max[1] = l[0]+l[1]
# 12, 02
if n >= 3:
    l_max[2] = max(l[1]+l[2], l[0]+l[2])
# 134 24
if n >= 4:
    for nn in range(3, n):
        l_max[nn]= max(l[nn] + l_max[nn-2], l[nn] + l[nn-1] + l_max[nn-3])

# print(l)       
# print(l_max)
print(l_max[n-1])

 

조건이 세개 있다

1. 무조건 마지막 계단은 밟아야한다
2. 세번을 연속으로 1칸씩 밟을 수는 없다
3. 2칸 이상으로는 건너 밟을 수 없다

• 만약 계단이 1개면?
  • 해당 계단을 하나만 밟으면 된다
    • 0번 계단 (index 0부터 시작)
• 만약 계단이 2개면?
  • 두 계단을 모두 밟으면 된다
  • 0, 1번 계단
• 만약 계단이 3개면?
  • 세 계단을 모두 밟을순 없고 → 0, 1, 2 불가
  • 마지막 계단을 무조건 밟아야 하고 → 2은 무조건 고정
  • 2칸 이상은 건너 밟을 수 없다 → 그냥 2 은 불가
  • 그럼 가능한 수는
    • 0, 2
    • 1, 2
• 만약 계단이 4개 이상이라면?
  
  • 마지막에 붙어있는게 연속되어있는지는 알 수 없기에
  • ~ 01 3는 보장할 수 없고
  • ~ 1 3 은 가능 (앞에 뭐가 있든 1칸 넘어서 가는건 된다)
  • ~ 0 23 도 가능 (앞에서 1칸 뛰어 넘어놓으면 그 다음에는 붙어 건너도 된다)

여기서 앞에 뭐가 붙든 뒤에서 값을 추가하면서 체크해도 된다는걸 알면 dp 문제임을 알 수 있다.

(최적 부분 구조, 중복되는 부분 메모이제이션)

 

따라서 4이상일때 점화식이 다음과 같다

dp[n] = max( stair[n] + stair[n-1] + dp[n-3], stair[n] + dp[n-2] )

 

 

점화식만 알게되면 그대로 코드로 풀면된다

 

점화식을 찾는 과정이 중요하다...

점화식을 찾는 연습이 반드시 필요한것같다