2579 - 계단 오르기

 

---

 

문제

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

2579번: 계단 오르기

 

풀이

dp 방식으로 생각해보면 '내가 위치한 계단을 어떻게 오느냐' 에 초점을 맞춰보면 된다.

 

내가 i번째 계단에 있다면 나는

1. i-1 번째 계단에서 왔거나

2. i-2 번째 계단에서 왔을것이다.

 

단 i-1번째 계단에서 왔다면, i-2번째계단을 밞고오진 않았을 것이다. (그렇게 되면 3개 연속 계단을 밞으니)

따라서 i-3 번째에서 왔을것이고 이를 활용하여 점화식을 세울 수 있다.

 

D[i] = max ( D[i-2] + 계단값[i] , D[i-3] + 계단값[i-1] + 계단값[i] ) 

 

 

코드

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

answer = 0

# 계단이 1개면
if n == 1:
    d[1] = vals[1]
# 계단이 2개면
if n == 2:
    d[2] = vals[1] + vals[2]
# 계단이 3개면
if n == 3:
    d[3] = max(vals[1] + vals[3], vals[2] + vals[3])


# 계단이 4개 이상이면
if n >=4:
    d[1] = vals[1]
    d[2] = vals[1] + vals[2]
    d[3] = max(vals[1] + vals[3], vals[2] + vals[3])

    for i in range(4, n+1):
        d[i] = max(d[i-3] + vals[i-1] + vals[i], d[i-2] + vals[i])

print(d[n])