[백준/Python] 2579 계단 오르기

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

2579번: 계단 오르기

 

계단이라고는 하지만, 이전의 DP문제와 흡사한 방식이다.

조건이 여러 가지이므로 이를 모두 충족시켜야 하는데, 그러지 못해 계속 제출 실패를 했다.

또한 백준에서 제시한 테스트케이스 이외에 다른 케이스를 생각하지 못해 런타임 에러가 발생....^^ 

 

조건은 다음과 같다.

 

규칙을 찾아보면,

dp[i] 는 현재 계단과 전 계단을 밟은 경우의 합이거나, 현재계단과 전 계단을 밟지 않은 경우의 합 중 큰값을 저장해야 한다. 

 

즉, 현재 계단(array[i])과 전 계단을 밟은 경우(array[i-1] + dp[i-3])의 합과

( >> 이때 dp[i-3]을 해주는 이유는 세 개의 계단을 연속으로 밟을 수 없기 때문에,

array[i-2]가 아닌 array[i-3]의 인덱스까지 구해져 있던 최댓값을 불러와 주는 것이다.)

현재계단(array[i])와 전 계단을 밟지 않은 경우(dp[i-2])의 합 중 max값을 저장해주는 것이다. 

 

이때 i-3이라는 조건이 들어가기에 for문은 3부터 시작하고, 

dp[0~2]까지는 하드코딩을 해준다.

 

 

그리고 또 주의할 점!

계단이 1일 때, 2일 때는 식이 성립하지 않으므로 

조건문을 통해 처리해 주어야 한다. 

 

n = int(input())

array = []
for i in range(n):
    array.append(int(input()))

dp = [0]*n

if n == 1:
    print(array[0])
elif n == 2:
    print(array[0] + array[1])    

else:
    dp[0] = array[0]
    dp[1] = max(array[0]+array[1], array[1])
    dp[2] = max(array[0]+array[2], array[1]+array[2])

    for i in range(3, n):
        dp[i] = max(array[i]+dp[i-2], array[i]+array[i-1]+dp[i-3])

    print(dp[n-1])

 

계단이 1과 2일 때 성립하지 않는다는 것을 전혀 고려하지 않아...^^ 문제 해결에 애를 먹었다. 

조건 하나하나를 신경 쓰고, 내가 무심코 가정해버린 케이스는 없는지 꼼꼼히 따지도록 더욱 연습해야겠다.