[백준] 2579번 계단 오르기(파이썬)

문제

2579번: 계단 오르기

코드

n = int(input())
stair = [0]
score = [0] * (n+1)
for i in range(n):
  stair.append(int(input()))
  # 한칸에서 두번째 칸은 점화식에서 이용되는 수이자 max값이 바뀔일이 없으니 먼저 설정한다.
  if i < 2:
    score[i+1] = sum(stair[0:i+2])

# 설정이 인된 3부터 돌아준다
for i in range(3, n+1):
    # score[i-2]+stair[i] : 1칸 2칸 가는경우(그림의 파란색)
    # score[i-3]+stair[i-1]+stair[i] : 2칸 1칸 가는경우(그림의 빨간색)
    score[i] = max(score[i-2]+stair[i], score[i-3]+stair[i-1]+stair[i])
print(score[-1])

해설

3번째 칸에 오르는 방식은 2가지 방법이 있다.

파란색과 같이 1칸 2칸을 오르는 방법과 빨간색과 같이 2칸 1칸을 오르는 방법이다.

이 경우1번째칸과 2번째칸은 각각 10, 30(4번째 칸을 갈때 파란색 점프로 사용하기 위해)을 넣어주고 시작해야한다.

그리고 3번쨰 칸부터 다음과 같은 점화식으로 구한 수 중 큰 수를 저장해준다.

score[i] = score[i-2]+stair[i]
score[i] = score[i-3]+stair[i-1]+stair[i]

느낀점

다이나믹 프로그래밍을 몇개 풀어보니까. 코드로 구현하기에 난감하다. 강좌를 보니 못하겠으면 30분 생각해보다가 답안코드를 보고 작성해 보라고 하셨다. 그렇게 몇개를 풀어보니 규칙성을 발견하는게 중요하다는 생각이 들었다. 그리고 실제 답안을 보니 내가 규칙을 만들려고 노력해서 생각이 안났던게 관점을 바꿔보니 이렇게 되네? 하는게 많았다. 앞으로 문제를 풀면서 규칙성을 다양한 관점으로 찾는 연습을 해야할 것 같다.