[백준][C#] 2579 계단 오르기 - 실버3

문제보기

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

2579번: 계단 오르기

 

 

언뜻 보아도 DP(다이나믹 프로그래밍)를 사용하는 문제이다.

 

마지막 계단까지 점수의 Max 값을 구하면 되지만,

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

조건이 까다롭기 때문에 점화식을 잘 세우는 것이 관건이었다.

 

3번 조건이 "마지막 도착 계단은 반드시 밟아야 한다."이기 때문에,

마지막 계단을 기준으로 경우의 수를 따져본다.

// dp는 index의 계단까지 score 최대 합,
// score은 index의 계단에 써진 score이다.

// 경우의 수 1
dp[n] = dp[n-2] + score[n]
// 경우의 수2
dp[n] = dp[n-3] + score[n-1] + score[n]

1칸 또는 2칸을 오를 수 있기 때문에

n번째 칸과 n-1번째 칸까지의 합

n번째 칸과 n-2번째 칸까지의 합

이라는 경우의 수가 있다고 할 수 있다.

이 중 n번째 칸과 n-1번째 칸까지의 합의 경우, 연속 세 개의 계단을 모두 밟아서는 안 된다는 규칙이 있기 때문에 n-3번째 칸까지의 합 + n-1번째 칸 + n번째 칸으로 변경하여야 반례를 없앨 수 있다.

 

 

주의점

경우의 수2에서 dp[n-1]이 아닌 score[n-1]이다.

dp[n-1]을 더해버린다면 n-3까지의 합과 n-1까지의 합이 들어가버려 틀린 답이 되어버린다.

 

코드 보기

        static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int n = int.Parse(reader.ReadLine());
            int[] floors = new int[301];
            
            for(int i = 0; i < n; i++)
            {
                floors[i] = int.Parse(reader.ReadLine());
            }

            int[] dp = new int[301];
            dp[0] = floors[0];
            dp[1] = floors[0] + floors[1];
            dp[2] = Math.Max(floors[0] + floors[2], floors[1] + floors[2]);
            for (int i = 3; i < floors.Length; i++)
            {
                dp[i] = Math.Max(dp[i - 3] + floors[i - 1] + floors[i], dp[i - 2] + floors[i]);
            }

            print.WriteLine(dp[n - 1]);
        }