백준 2579 [python]

내 풀이

1. 목적지에서 시작하여 시작 지점까지 재귀 함수를 호출한다.

2. 목적지로 올 수 있는 경우에 대해 최대값을 구하고 최대값에 현재 계단의 값을 더해 최대값을 구한다.
   Ex) 5번째 계단의 경우 3번과 4번에서 올 수 있으므로 둘 중 최대값을 구하고 5번째 계단의 값을 더해 최대값을 구한다. 

3. 연속으로 세번 이동하는 경우에 대한 예외 처리를 해주기 위해 cnt 값이 3이 되면 0을 반환하게 한다.

4. 목적지에 따라 오는 경우의 수의 최대값이 다르기 때문에 이를 고려하여 dp 테이블을 생성한다.
   특정 목적지로 오기 위한 최대값이므로 다름 
   Ex) 4번에 도착하기 위한 2번의 최대값과 3번에 도착하기 위한 2번의 최대값이 다를 수 있음 
   몇 번째 계단인지랑, 연속으로 몇 번 이동했는지를 기준으로 최대값을 dp 테이블에 저장한다.

5. dp 테이블에 데이터가 존재하면 바로 반환하고 그렇지 않으면 재귀 호출을 통해 처리한 후 결과를 dp 테이블에 저장
   그리고 해당 dp 테이블 결과를 반환 

내 코드

import sys 

arr = list()
N = int(sys.stdin.readline().rstrip())

arr.append(0)
for i in range(N) :
    arr.append(int(sys.stdin.readline().rstrip()))

dp = [[-1] * 3 for i in range(N+1)]
def stairUp(arr, idx, cnt) :

    # 출발점에 도달했거나, 3번 연속 이동하는 경우
    if idx == 0 or cnt == 3:
        return 0

    if dp[idx][cnt] != -1 : 
        return dp[idx][cnt]

    first = 0
    second = 0

    if idx - 1 >= 0 :
        first = stairUp(arr, idx-1, cnt + 1)

    if idx - 2 >= 0 :
        second = stairUp(arr, idx-2, 1) 
    dp[idx][cnt] = max(first, second) + arr[idx]  
    return dp[idx][cnt]

print(stairUp(arr, len(arr) - 1, 1))

마무리

될 것 같기도 하고 안 될 것 같기도 하면 생각만 하지 말고 바로 코드로 구현해보면서 가능한지 확인해봐야겠다.
생각만 하면 시간만 지나간다. 마치 '고민은 배송을 늦출 뿐'이란 말과 비슷한 것 같다.
'불필요한 생각은 구현만 늦출 뿐'

결과