백준알고리즘 2579번 계단 오르기 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 2579
• 문제명: 계단 오르기
• 언어: C#
• 분류: 다이나믹 프로그래밍
• 비고: 

 

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

 

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

 

계단 오르는 데는 다음과 같은 규칙이 있다.

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

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

 

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

 

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

 

풀이

Math.Max()는 콤마로 2개의 값을 구분하며 1개의 값이 연산식일 때는 연산을 먼저 하고 최종 값을 받아 서로 비교한다.

// 계단의 개수 입력
int testCase = Convert.ToInt32(Console.ReadLine());
// 계단에 쓰여 있는 점수
int[] stairScore = new int[testCase + 1];
// 게단을 오르면서 얻는 점수
int[] score = new int[testCase + 1];

// 계단 칸마다 점수 적용
for (int i = 1; i <= testCase; i++)
    stairScore[i] = Convert.ToInt32(Console.ReadLine());

// 계단의 첫번째 칸에 점수 적용
score[1] = stairScore[1];

// 계단의 개수가 1개를 초과한 경우 첫 번째 계단과 두 번째 계단의 점수를 합한 점수를 적용한다.
if (testCase > 1) score[2] = stairScore[1] + stairScore[2];

// 세번째 계단부터의 점수 계산
// 1. i - 2번째 계단에서 얻은 점수, i - 3번째 계단에서 얻은 점수와 i - 1번째 계단에 쓰인 점수의 합을 비교한다.
// 2. 비교 후 더 큰 값에 i번째 계단에 쓰인 점수를 더한다.
for (int i = 3; i <= testCase; i++)
    score[i] = Math.Max(score[i - 2], score[i - 3] + stairScore[i - 1]) + stairScore[i];

// 도착 후 최대 점수 출력
Console.WriteLine(score[testCase]);

 

후기

그리하여 다이나믹 프로그래밍 주가 마감되고 내일부터 자료 구조의 주가 시작된다. 다이나믹 프로그래밍을 온전히 자력으로 풀어 볼 정도로 실력을 키워야 한다. 그러면 대체 무엇을 해야 할까?