[백준] 2579번 계단 오르기 (Python, DP)

<문제 링크>

백준 2579번 계단 오르기

---

문제 요약

점수가 있는 계단을 오르는데, 아래 규칙에 맞춰 올랐을 때 점수의 최대값을 구하는 문제이다.

1. 계단은 1칸 혹은 2칸씩 오를 수 있다.
2. 연속으로 3개의 계단을 밟을 수 없다. 하지만 시작점은 계단에 포함되지 않는다.
   -> 1칸씩 2번 오를 수 없다. (1->2->3 X)
   -> 즉, 1칸 오르면 그 다음은 무조건 2칸을 올라야 한다.
3. 마지막 도착은 꼭 마지막 계단을 밟아야 한다.

ex0)

• 계단 개수 : 6
• 첫번째부터 마지막까지 각 계단의 점수
  -> 10 / 20 / 15 / 25 / 10 / 20
• 정답 : 75
  -> 10 - 20 - 25 - 20
  

---

문제 풀이

본 문제는 DP 알고리즘을 활용해 해결할 수 있는 문제이다.
문제에서 주어진 규칙 3번을 보면, 결국 마지막 계단은 거쳐야 하는 것이니,
계단 개수를 1부터 주어진 개수까지 늘려가며 각 칸마다 최대값이 도출되는 규칙을 찾아보자.

문제 요약의 ex0) 예시를 토대로 찾아보면,

(n번째 계단에서의 최대값을 MS(n)으로,
n번째 계단의 점수를 S(n)으로 설정한다.)

<1칸만 주어졌을 때>

• 계단 : 10
• MS(1) : 10

<2칸까지 주어졌을 때>

• 계단 : 10 / 20
• MS(2) : 10 + 20

여기까지는 규칙을 찾기 어렵다.

<3칸까지 주어졌을 때>

• 계단 : 10 / 20 / 15

3칸부터 조금씩 고민해 볼 필요가 있다. 문제에서 주어진 규칙 1번과 2번을 토대로 생각해 보면, 3번째 칸에서 최대값은 다음 둘 중에 하나로 정해진다.

1. 2번째 칸에서 한칸오르기
   -> 한칸 오르기는 2번 연속 있을 수 없기 때문에, 다음과 같이 오를 것이다.
   -> 0 - 2 - 3
   -> S(2) + S(3) = 20 + 15
2. 1번째 칸에서 두칸오르기
   -> 1 - 3
   -> S(1) + S(3) = 10 + 15

여기서 주의깊게 봐야하는 점은 결국 마지막 계단에서는 한칸 앞에서 오르거나, 두칸 앞에서 올라야 한다는 것이다.

따라서 3칸의 최대값은 다음과 같다.

• MS(3) : max(한칸 앞에서 오기, 두칸 앞에서 오기)
  -> max(S(2)+S(3), S(1)+S(3))
  -> max(20+15, 10+15) == 20 + 15

<4칸까지 주어졌을 때>

• 계단 : 10 / 20 / 15 / 25

4번째 칸의 최대값은 다음 둘 중에 하나로 정해진다.

1. 3번째 칸에서 한칸오르기
   -> 한칸 오르기는 두번 연속 못하기 때문에, 3번째 칸은 무조건 1번째 칸에서 올랐을 것이다.
   -> 1 - 3 - 4
   -> S(1) + S(3) + S(4) = 10 + 15 + 25
2. 2번째 칸에서 두칸오르기
   -> 이 경우는 2번째칸의 최대값을 더해야 본인도 최대값이 될 것이다.
   -> MS(2) + S(4) = 30 + 25

여기서 주의깊게 봐야하는 점은, 두칸 앞에서 올 때는 결국 두칸 앞의 최대값이 더해져야 한다는 것이다.

4번째 칸과 2번째 칸은 두칸 차이가 나기 때문에, 2번째 칸까지 올라올 수 있는 방법도 다음 두가지로 나누어 진다.

1. 1번째 칸에서 한칸오르기
2. 0번째 칸(시작점)에서 두칸오르기

이 두가지 경우 모두 2번째 칸의 최대값에 반영되어 있기 때문에, 2번째 칸에서 4번째 칸으로 가는 경우는 그냥 2번째 칸의 최대값만 더해주면 되는 것이다.

이를 '3번째 칸에서 한칸 오르기'에 적용해보면, 결국 다음과 같이 정해질 수 있다.

• S(1) + S(3) + S(4)
  -> S(1)과 S(3)은 두칸 차이 난다.
  -> S(1)은 꼭 최대값이어야 한다.
  -> 결국 MS(1) + S(3) + S(4) 인 것이다.
  (원래는 MS(1)이어야 하는데, 첫번째 칸이라 눈에 안띄는 것이다)

따라서 4칸의 최대값은 다음과 같다.

• MS(4) : max(한칸 앞에서 오기, 두칸 앞에서 오기)
  -> max( MS(1) + S(3) + S(4), MS(2) + S(4))
  -> max(10+15+25, 30+25) == 30+25

<5칸까지 주어졌을 때>

• 계단 : 10 / 20 / 15 / 25 / 10

5번째 칸의 최대값도 똑같이 다음 둘 중 하나로 정해진다.

1. 4번째 칸에서 한칸오르기
   -> 똑같이 4번째 칸은 무조건 2번째 칸에서 올랐을 것이다.
   -> 1 - 2 - 4 - 5
   -> 여기서 "1 - 2"는 결국 2번째 칸의 최대값이다.
   -> MS(2) + S(4) + S(5) = 30 + 25 + 10
2. 3번째 칸에서 두칸오르기
   -> 3번째 칸에서 두칸 올라와 최대값을 만드려면, 3번째 칸까지가 일단 최대값이 되어야 한다.
   -> MS(3) + S(5) = 35 + 10

따라서 5칸의 최대값은 다음과 같다.

• MS(5) : max(한칸 앞에서 오기, 두칸 앞에서 오기)
  -> max( MS(2) + S(4) + S(5), MS(3) + S(5))
  -> max(30+25+10, 35+10) == 65

여기까지 와보면 규칙이 보이고, 점화식으로 나타낼 수 있다.

한칸 앞에서 올 때 : MS(n-3) + S(n-1) + S(n)
두칸 앞에서 올 때 : MS(n-2) + S(n)
=> MS(n) = max(MS(n-3) + S(n-1) + S(n), MS(n-2) + S(n))

---

구현

이제 구한 점화식을 그대로 구현하면 된다.

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

ansList = [0]*(n+1)
ansList[1] = stairs[1]

if n > 1:
    ansList[2] = stairs[1]+stairs[2]

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

print(ansList[n])

stairs에 계단의 점수가 저장되고,
ansList에 각 계단에서의 최대값이 저장된다.

ansList[i] = max(ansList[i-3]+stairs[i-1] +
                         stairs[i], ansList[i-2]+stairs[i])

위 코드에서 점화식을 찾아볼 수 있다.