백준 [2579]: 계단 오르기

📌 백준 [2579]: 계단 오르기

🔗 문제 링크

---

문제 설명 📄

계단을 오를 때 다음 규칙을 따라야 한다:

1. 계단은 한 번에 한 계단 또는 두 계단씩 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다.
3. 마지막 계단은 반드시 밟아야 한다.

각 계단에는 점수가 있으며, 계단을 밟을 때 그 점수가 더해진다. 계단의 점수가 주어질 때, 얻을 수 있는 총 점수의 최댓값을 구하시오.

---

문제 접근 방식 💡

• 동적 프로그래밍(DP)을 사용하여 최댓값을 계산.
• 각 계단에서 얻을 수 있는 점수를 dp[i]로 정의.
• 규칙을 만족하며 마지막 계단을 밟는 경우를 고려해 점수를 누적.

---

Solution 💻

stairs = [int(input()) for _ in range(int(input()))]

if len(stairs) == 1:
    print(stairs[0])
elif len(stairs) == 2:
    print(stairs[0] + stairs[1])
else:
    dp = [0] * (len(stairs))
    dp[0] = stairs[0]
    dp[1] = stairs[1] + dp[0]
    dp[2] = max(stairs[2] + stairs[0], stairs[2] + stairs[1])

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

    print(dp[-1])

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 계단의 개수만큼 반복문을 실행하므로 선형 시간 소요.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • 계단 개수만큼의 dp 배열을 사용.

---

리팩토링 🛠️

stairs = [int(input()) for _ in range(int(input()))]

if len(stairs) == 1:
    print(stairs[0])
elif len(stairs) == 2:
    print(stairs[0] + stairs[1])
else:
    prev1 = stairs[0]
    prev2 = stairs[1] + prev1
    curr = max(stairs[2] + stairs[0], stairs[2] + stairs[1])

    for i in range(3, len(stairs)):
        curr = max(stairs[i - 1] + prev1 + stairs[i], prev2 + stairs[i])
        prev1, prev2 = prev2, curr

    print(curr)

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 계단의 개수만큼 반복문을 실행.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(1)
  • DP 배열을 제거하고 상수 크기의 변수만 사용.