[Algorithm] DP - 백준2579 계단 오르기

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 사이트의 2579번 계단 오르기 문제를 해결한 과정을 정리하려고 합니다.

 

해당 문제는 다음과 같습니다.

 

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

 

<문제 규칙>

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

해당 문제는 DP를 활용하여 해결할 수 있습니다.

 

1. 문제 풀이 과정

 

밟은 계단은 파랑색, 안 밟은 계단은 회색으로 처리하였습니다.

 

• if (n == 1) ? 
  n == 1이면, 무조건 계단을 밟아야 하므로, 10입니다.

 

• if (n == 2) ?
  n == 2이면, 1번과 2번 계단을 밟아야 최대이므로, 답은 35입니다.

• if ( n == 3)?
  n == 3이면, 1번 계단과 2번 계단 중, 큰 값을 선택하여 밟은 후, 3번째 계단을 밟아야 합니다.

• if (n >= 4)?
  DP가 적용되기 시작하는 과정이라고 볼 수 있습니다.

 

• if (n == 4)
  • 최댓값이라고 가정하여 밟을 수 있는 가지수는 크게 두가지 입니다. 연속해서 3개의 계단을 밟을 수 없으므로,
  • 1) 1번 + 3번 + 4번 => 10 + 15 + 25 = 50
  • 2) 1번 + 2번 + 4번 => 10 + 20 + 25 = 55
  • 즉, 1번 + 2번 + 4번을 밟는다면 55의 점수를 얻습니다.

 

• if (n==5)
  • 1) 1번 + 2번 + 4번 + 5번 => 10 + 20 + 25 + 10 = 65
  • 2) 2번 + 3번 + 5번 => 20 + 25 + 10 = 55

 

이를 활용하여, 규칙을 확인할 수 있습니다.

만약 i 번째 계단이 있다면,

계단은 (i - 3) 번째의 얻을 수 있는 점수의 최대값 + (i - 1) 번째의 계단의 점수를 더한 값과 (i - 2) 번째의 점수의 최댓값을

비교하여 i번째 계단의 값을 더하면 최대 점수의 값을 구할 수 있습니다.

따라서, 30 + 25 + 10인 65가 됩니다.

 

따라서, 주요 로직은 다음과 같습니다. (scores는 i번째의 계단의 최대값을 기록하는 dp 스코어 배열, arr은 각 계단의 점수 배열)

scores[i] = Math.max(scores[i - 3] + arr[i - 1], scores[i - 2]) + arr[i];

 

2. 자바 알고리즘 코드 

최종 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main2579 {

    static int n;
    static int[] arr;
    static int[] scores;

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(bf.readLine()); // 입력받는 개수
        arr = new int[n]; // 입력받는 배열
        scores = new int[n]; // 점수 dp 스코어

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(bf.readLine());
        }

        long result = calculateDpScore();
        System.out.print(result);

    }

    static long calculateDpScore() {

        if (n == 1) {
            return arr[0];
        }

        else if (n == 2) {
            return arr[0] + arr[1];
        }

        scores[0] = arr[0];
        scores[1] = arr[0] + arr[1];
        scores[2] = Math.max(arr[0], arr[1]) + arr[2];

        for (int i = 3; i < n; i++) {
            scores[i] = Math.max(scores[i - 3] + arr[i - 1], scores[i - 2]) + arr[i];
        }

        return scores[n-1];
    }

}

이상으로 백준 2579번의 계단 오르기 알고리즘 정리를 마치겠습니다.

감사합니다.!!!

 

문제:

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