파이썬) 계단 오르기 - BOJ

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

2579번: 계단 오르기

 

이 문제는 알고리즘 dp문제였다.

처음 이 문제를 접했을 때, 당연히 dfs로 풀 수있는 문제라 생각했고 실제로 그렇게 코드를 작성해나갔다.

 

n = int(input())

arr = []

for _ in range(n):
    arr.append(int(input()))


result = -1

def dfs(idx,sums,his):
    store = arr[idx]
    if idx == n -1:
        global result
        result = max(result,sums)
        return


    if idx + 2 <= n-1 :
        new_his = his
        if len(new_his) == 3:
            new_his.pop(0)

        new_his.append(idx)

        dfs(idx+2,sums+store,new_his)

    if len(his) < 3:

        new_his = his
        his.append(idx+1)

        dfs(idx+1, sums+store,new_his)

    else:


dfs(0,0,[])

그렇게 작성을 이어가는 중 문득 이상함을 느꼈다.

his가 비었을 경우, 그리고 his가 2이하인 경우를 나눠 현재있는 계단 + 1이 세 계단 연속인지 아닌지를 판별하며 많은 if 분기점을 작성해야한다는 점(물론 더 쉽게 if문을 작성할 수 있겠지만)에서 의문을 느꼈다.

 

곰곰히 생각을 해보았고 알고리즘 분류로 dp가 선택되어 있는 것으로 보아 dp를 이용하기로 했다.

n = int(input())

arr = [0]*301

for i in range(1, n+1):
    arr[i] = int(input())

dp = [0] * 301

dp[1] = arr[1]
dp[2] = arr[1] + arr[2]

dp[3] = max(arr[1] + arr[3], arr[2]+arr[3])

for i in range(4, n+1):
    # 한칸 전에서 온 경우는 현재 있는 곳 -1번째에서 오지 않았다(세계단 연속으로 할수 없음)
    # 그러므로  dp[i - 3]값과 arr[i-1], arr[i]번째를 구해야한다.
    
    # 반대로 -2번째 칸에서 온 경우 dp[i - 2]번째 칸과 현재 칸을 더해 구해주었다.
    dp[i] = max(dp[i-3] + arr[i-1] + arr[i], arr[i] + dp[i-2])

print(dp[n])

 

생각해보자

 

10

20

15

25

10

20

 

현재 칸이 4번째 칸이라 생각해보겠다 (인덱스가 1부터 시작했을 때.)

그럼 현재 칸에 온 경우는 두가지로 나뉜다.

1. 바로 직전 칸(3)에서 온 경우
2. 전전칸(1)에서 온 경우

전전칸에서 온 경우는 이미 dp로 구해놓았다. 결국 전전 칸의 경우는 그 값이 최선의 값이다.

반면 바로 직전 칸에서 온 값은 세 계단 연속으로 올 수 없음을 고려했을 때 그 값이 최선의 값이라 생각할 수가 없다.

때문에 바로 직전칸의 경우 다음으로 생각할 수 있다. 

직전칸의 값과 전전칸의 dp값.

때문에 코드는 다음과 같을 수 밖에 없다.

 

dp[i] = max(dp[i-3] + arr[i-1] + arr[i], arr[i] + dp[i-2])