[Baekjoon/🥈SilverⅢ] 2579: 계단 오르기

Intro

• 문제를 요약한다면 다음과 같다.

  • n개의 계단이 있으며, 각 계단마다 점수가 존재한다.

  • 계단을 올라 얻을 수 있는 최대의 점수를 출력하자!

    🙄 단, 규칙은 다음과 같다.

    • 계단은 한 번에 하나, 혹은 두 개씩 오를 수 있다.
    • 연속해서 세 계단을 밟을 수 없으며, 시작점은 제외한다.
    • 마지막 도착 계단은 반드시 밟는다.

접근 방법🙋‍♀️

• 연속 세 계단을 밟을 수 없으므로 i번째 계단을 밟는 방법은 다음과 같이 두 가지 경우가 존재한다.

  • i-2번째 계단을 밟지 않고, i-1과 i번째 계단을 밟는 경우

    • i-1과 i번째 계단을 밟기 위해서는 i-3번째 계단을 밟아야 한다.
    • i-3 이전 계단을 밟았는지는 중요하지 않다.

  • i-1번째 계단을 밟지 않고, i-2와 i번째 계단을 밟는 경우

    • i-2가 이전 계단을 밟았는지는 중요하지 않게 된다.

이를 통해서 우리는 다음과 같은 사실을 알 수 있다.

👩 i번째 계단을 밟아 얻을 수 있는 최대의 점수를 구하기 위해서는 다음의 두 값이 필요하다.

• i-2번째 계단을 밟았을 때 얻을 수 있는 최대 점수

• i-3번째 계단을 밟았을 때 얻을 수 있는 최대 점수

따라서 우리는 해당 문제를 동적계획법을 적용해 해결할 수 있다.

Algoritm👩‍💻

위 방식을 적용해 알고리즘을 작성해보자!

#21.10.12
import sys
N = int(input())

# 두 번째 계단부터 기본연산을 적용할 수 있도록 2개의 0을 리스트에 넣어둔다.
score = [0, 0]
dp = [0, 0]

for i in range(N):
  score.append(int(sys.stdin.readline().rstrip()))
dp.append(score[2])

# 첫 번째 계단은 for문이 시행되지 않고 해당 계단의 점수가 바로 출력되게 된다.
# 그 이후 계단부터는 다음의 두 값을 비교해 최대 값을 넣게 된다.
  # i-2와 i번째 계단을 밟을 경우
  # i-3과 i-1, i번째 계단을 밟을 경우
for i in range(3, N+2):
  temp1 = score[i] + dp[i-2]
  temp2 = score[i] + score[i-1] + dp[i-3]
  dp.append(max(temp1, temp2))

print(dp[-1])

• 🙋‍♀️ 여기서 주의할 점!!

  • i-3과 i-1, i번째 계단을 밟을 경우

    • i-1를 밟고 이전 계단인 i-2를 밟지 않아야 한다.

      = dp[i-3] + score[i-1] + score[i]

      • i-3 이전 계단의 경우, 밟았는지 여부가 상관없으므로 dp[i-3]을 통해 i-3 계단을 밟았을 때 얻을 수 있는 최대 점수를 구한다.
      • 추가로 score[i-1], score[i] 값을 더해 i-3을 밟았을 때의 최대 점수를 얻을 수 있는 방법에서 i-1과 i를 밟는 경우의 점수를 계산한다.

👩 그럼 이만 마무리하도록 한다!!

이만!

끝! ~(˘▾˘~)

📃참고

• https://sungmin-joo.tistory.com/18
• https://pacific-ocean.tistory.com/149