[백준] 2579: 계단 오르기 - 파이썬[python]

많은 걸 고려해야 하는 문제로 꽤 많은 시행착오를 겪었다 ㅎ

풀이

• 이 문제는 점화식을 찾아야 하는 문제이다! 전에 문제에 갇혀 그냥 앞에 애들의 max를 구하려고 했더니 규칙을 만족시키면서 풀 수가 없더라,,
• 이럴 때 규칙을 찾아 점화식을 찾아보자!! 이제 점화식이 어떨 때 떠올리면 되는지 대충 감을 찾은 것 같다.
• 점화식이란 걸 떠올리지 못했고,, 점화식을 찾는 데 해당 게시글이 많은 도움을 주었다.
• 아무튼 점화식을 떠올리는 과정은 아래와 같다.
  1. n번째 계단은 바로 전 계단에서 오르거나 전전 계단에서 오를 수 있다.
  2. 그런데 전 계단에서 오를 경우에는, 전 계단은 무조건 전전 계단에서 올라야 한다. 계단을 3개 연속해서 오를 수 없기 때문이다.
  3. 따라서 n번째 계단은 'n-3번째 계단->n-1번째 계단->n번째 계단' 혹은 'n-2번째 계단->n번째 계단'과 같은 과정을 통해 오를 수 있다.
  4. 이제 우리는 둘 중에 더 큰 값이 뭔지를 찾으면 되기에 이를 점화식으로 표현해보자.
  5. DP[n] = max(DP[n-3] + stair[n-1], DP[n-2]) + stair[n]가 된다.
  6. 이 점화식은 n=3부터 가능하기에 DP에 0~2인덱스 값은 따로 저장해야 된다.

시행착오

• 위의 점화식은 잘 이해했는데.. 2가지 간과한 점이 있어서 바로 문제를 맞히진 못했다.

틀렸습니다.

• 3번째 계단을 오르는 방법을 잘못 생각했다.
• 1번째 계단은 무조건 올라야 한다고 생각해서 3번째 계단을 오르는 방법은 1->3밖에 없다고 생각했다.
• 그런데 문제를 다시 보니 1번째 계단은 무조건 밟아야 된다는 말은 없다. 시작점이 계단이 아니라는 말뿐이다.
  그래서 시작점에서 바로 1번째 계단 혹은 바로 2번째 계단으로 가도 된다.
• 따라서 3번째 계단은 1->3 혹은 2->3 중에서 큰 값으로 오르면 된다.

런타임 에러

• 접근가능한 인덱스를 고려한다고 DP에 값을 저장하는 방법은 n=3부터로, append를 이용해서 잘 했는데..
• 3번째 계단을 저장하는 코드를 잘 보면

DP = [stair[0], stair[0]+stair[1]]
DP.append(max(stair[0]+stair[2], stair[1]+stair[2]))

n=1이거나 n=2일 때는 stair[1]이나 stair[2]에 접근하지 못해 런타임 에러가 발생하게 된다.

• 따라서 우리는 n<=2일 때는 그냥 계단을 다 오르는 게 최댓값이므로 계단을 모두 더해서 출력해주면 된다.

코드

import sys
input = sys.stdin.readline

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

if n<=2:
    print(sum(stair))
else:
    DP = [stair[0], stair[0]+stair[1]] # 첫째 줄 계단은 무조건, 둘째 줄 계단은 1->2가 시작->2보다 큼
    DP.append(max(stair[0]+stair[2], stair[1]+stair[2])) # 셋째 줄은 1->3 혹은 2->3
    for i in range(3, n):
        DP.append(max(DP[i-3] + stair[i-1], DP[i-2]) + stair[i])

    print(DP[n-1])

결과

• 아직 많이 부족하구만.. 그래도 재밌었던 문제