[백준 - 2579] 계단 오르기 - Java

문제 설명

 

 

2579번: 계단 오르기

 

풀이 : Success

소스 코드

import java.util.Scanner;

class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int[] memo = new int[301];

        int[] steps = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            steps[i] = Integer.parseInt(sc.nextLine());
        }

        memo[1] = steps[1];
        if (n >= 2)
            memo[2] = steps[2] + steps[1];
        if (n >= 3)
            memo[3] = getMaxValue(steps[3] + steps[2], steps[3] + steps[1]);

        for (int i = 4; i <= n; i++) {
            memo[i] = getMaxValue(steps[i] + steps[i - 1] + memo[i - 3], steps[i] + memo[i - 2]);
        }

        System.out.println(memo[n]);
    }

    public static int getMaxValue(int a, int b) {
        return a >= b ? a : b;
    }

}

 

풀이 회고

해당 문제는 다이나믹 프로그래밍 방법을 이용했습니다.

 

우선 n = 1 ~ 4 까지의 규칙성을 찾으려고 노력했습니다.

 

규칙성을 유추해본 결과 n = 1, n = 2일 때는 단 하나의 경우의 수만 존재했습니다.

n = 3일 때는 2가지의 경우의 수가 존재했는데 첫번째 계단 + 마지막 계단인 경우 또는 두번째 계단 + 마지막 계단에 해당하는 경우입니다. 이때 마지막 계단은 반드시 도착한다는 전제 사항이 중요합니다.

n = 4일 때 역시 2가지의 경우의 수가 존재했는데 첫번째 계단 + 세번째 계단 + 마지막 계단인 경우 또는 첫번째 계단 + 두번째 계단 + 마지막 계단에 해당하는 경우입니다.

n = 4인 경우부터 메모라이즈된 값을 불러오도록 할 수 있었습니다.

 

우선 첫번째 계단 + 세번째 계단 + 마지막 계단인 경우 첫번째 계단까지의 메모라이즈된 값을 불러온 후 세번째 계단값과 마지막 계단값은 별도로 더해주는 식을 세울 수 있었습니다. 이는 계단을 연이어 3계단을 오를 수 없기 때문입니다.

또한 첫번째 계단 + 두번째 계단 + 마지막 계단인 경우 두번째 계단까지의 메모라이즈된 값을 불러온 후 마지막 계단값만 별도로 더해주는 식을 세울 수 있었습니다.

 

최종적으로 이 두 개의 값 중 더 큰 값이 문제에서 요구하는 계단값의 합 최대값이므로 이를 토대로 점화식을 세워 알고리즘을 구할 수 있었습니다.

 

 

참고자료

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