백준 2579번 계단 오르기 (C#)

오늘은 백준 2579번 계단 오르기 문제를 풀었다.
처음엔 단순히 계단을 오르면서 점수를 더하면 되는 줄 알았는데,
연속된 세 계단을 밟을 수 없다는 조건이 핵심이었다.

https://www.acmicpc.net/problem/2579

문제 조건 요약

• 계단마다 점수가 있다.

• 한 번에 1칸 또는 2칸을 오를 수 있다.

• 세 계단을 연속해서 밟을 수 없다.

• 마지막 계단은 반드시 밟아야 한다.

• 최대 점수를 얻는 경로를 구해야 한다.

접근 방식

처음에는 무작정 재귀나 for문으로 다 더해보려 했지만,
건너뛸 수도 있고, 세 계단을 연속으로 못 밟는 조건 때문에 복잡해졌다.

그래서 각 계단에 도달했을 때의 최댓값을 저장하는 방식으로 접근했다.
즉, dp[i]는 i번째 계단까지 왔을 때 얻을 수 있는 최대 점수를 의미한다.

정리

dp[0] = stair[0];
dp[1] = stair[0] + stair[1];
dp[2] = Math.Max(stair[0] + stair[2], stair[1] + stair[2]);

for (int i = 3; i < n; i++)
{
    dp[i] = Math.Max(
        dp[i - 2] + stair[i],
        dp[i - 3] + stair[i - 1] + stair[i]
    );
}

여기서 중요한 건 두 가지 경우를 고려하는 것이다:

• (i - 2) → i로 이동: 중간 계단 i-1을 건너뜀

• (i - 3) → (i - 1) → i: 두 계단을 연속 밟지만 세 계단 연속은 피함

즉, 이 점화식 안에 건너뛰는 경우가 자연스럽게 포함돼 있다.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace backjoon
{
    internal class Program
    {

        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            int[] stair = new int[n];
            for (int i = 0; i < n; i++)
            {
                stair[i] = int.Parse(Console.ReadLine());
            }

            if (n == 1)
            {
                Console.WriteLine(stair[0]);
                return;
            }

            if (n == 2)
            {
                Console.WriteLine(stair[0] + stair[1]);
                return;
            }

            int[] dp = new int[n];
            dp[0] = stair[0];
            dp[1] = stair[0] + stair[1];
            dp[2] = Math.Max(stair[0] + stair[2], stair[1] + stair[2]);

            for (int i = 3; i < n; i++)
            {
                dp[i] = Math.Max(dp[i - 2] + stair[i], dp[i - 3] + stair[i - 1] + stair[i]);
            }

            Console.WriteLine(dp[n - 1]);

        }
    }
}

느낀 점

처음에는 연속 3계단 금지 조건 때문에 많이 헷갈렸지만,
점화식을 정리하고 나니 생각보다 깔끔하게 해결됐다.