[백준/파이썬]2579 계단 오르기

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

2579번: 계단 오르기

 

문제

백준2579 계단 오르기

이게 어떻게 실버 3 문제인가?

 

두 시간 녹여준 문제다

 

처음에는 재귀로 풀었다가 메모리 초과가 났다.

 

그래서 DP로 풀어보려고 마음먹고 문제를 풀었는데

 

import sys
n = int(input())

arr = []
ans_arr = []
for i in range(n) :
    arr.append(int(sys.stdin.readline().rstrip()))
i = n - 1
count = 0

while True :
    if i < 0 :
        break

    if count == 1 :
        if i - 2 < 0 :
            break
        arr[i-2] += arr[i]
        count = 0
        i-=2

    else :
        if i - 1 >= 0 :
            sum1 = arr[i] + arr[i-1]
        else : sum1 = 0
        if i - 2 >= 0 :
            sum2 = arr[i] + arr[i-2]
        else : sum2 = 0


        if sum1 > sum2 :
            if i - 1 < 0 :
                break
            arr[i-1] = sum1
            count += 1
            i-=1

        else :
            if i - 2 < 0 :
                break
            arr[i-2] = sum2
            count = 0
            i-=2
    

    
print(max(arr))

이 코드다

 

뒤에 있는 계단부터 하나하나 카운트 해가며 두 칸, 한 칸 내려가는 경우를 체크하는 코드다. 뒤에서부터 한 이유는 마지막 계단은 꼭 들어가야 하기 때문이다.

 

그런데 채점해보니 광탈했다.

 

풀이를 찾아 봤다.

 

난 정말 이상하게 풀고 있었다.

 

 

내가 이해한 대로 풀이 과정을 설명하자면,

 

Arr리스트는 입력 리스트다.

 

DP[0] = Arr[0] -> 첫 번째 계단에서 나올 수 있는 최대점수

DP[1] = Arr[0] + Arr[1] -> 두 번째 계단에서 나올 수 있는 최대 점수

DP[2] = max(Arr[0]+Arr[2], Arr[1]+Arr[2] -> 세 번째 계단에서 나올 수 있는 최대 점수

 

여기 까지는 쉽게 이해가 됐다.

 

그런데 4번째 계단이 문제다.

 

나는 처음 4번째 계단은

DP[3] = max(DP[1]+Arr[3], DP[2]+Arr[3])으로 하면 될 줄 알았다.

(첫 번째 계단의 최대 점수 + 3번째 계단 점수 or 두 번째 계단의 최대 점수 + 3번째 계단 점수)

 

그런데 여기서 만약 DP[2]+Arr[3]으로 하게 되면 DP[2]가 Arr[1]+Arr[2]일때 한 칸씩 올라가는 경우가 3번 발생하기 때문에 문제의 조건이 지켜지지 않는다.

 

때문에 3칸 뒤에 있는 계단에서 2칸 올라온 값과 현재 계단 값을 더해줘야 한다. (한 칸 올라가는 경우가 2번만 발생하도록)

 

그래서 DP[3]은 DP[1]+Arr[3]과  DP[2]+Arr[3]이 아닌 DP[0]+Arr[3]+arr[2]중 더 큰 값으로 구해야 한다.

 

따라서 DP[3] = max(DP[1]+Arr[3], DP[0]+Arr[3]+Arr[2])가 된다.

 

이를 점화식으로 쓰면 

3 <= i < n

DP[i] = max(DP[i-2]+Arr[i], DP[i-3]+Arr[i]+Arr[i-1])이 된다!

 

DP[i-2] + Arr[i]는 전에 있던 계단에서 2칸 올라온 경우

DP[i-3] + Arr[i] + Arr[i-1]은 전에 있던 계단에서 1칸 올라온 경우다.

 

 

정답

import sys
n = int(input())

arr = []
dp = []
for i in range(n) :
    arr.append(int(sys.stdin.readline().rstrip()))

if n == 1 :
    print(arr[0])
    exit()
if n == 2 :
    print(arr[0]+arr[1])
    exit()
if n == 3 :
    print(max(arr[0]+arr[2], arr[1]+arr[2]))
    exit()
dp.append(arr[0]) 
dp.append(arr[0]+arr[1])
dp.append(max(arr[0]+arr[2], arr[1]+arr[2]))

for i in range(3, n, 1) :
    dp.append(max(dp[i-2] + arr[i], dp[i-3] + arr[i] + arr[i-1])) 

print(dp[n-1])