[JAVA/알고리즘] 백준 2579 계단 오르기 (DP)

 

Dynamic Programming 동적 계획법으로 해결 할 수 있는 문제이다.

 

DP 문제는 Top-down (재귀 함수), Down-up (반복문) 두 가지 방식으로 해결할 수 있다. 

 

 

아무점수가 없는 바닥을 step[0]이라고 하였을 때, 

 

계단이 n개 일 때 얻을 수 있는 점수의 최대값은

1) 계단이 n-2개일 때 얻을 수 있는 점수의 최대값 +  n번째 계단의 점수 

2) 계단이 n-3개일 때 얻을 수 있는 점수의 최대값 + n-1번째 계단 점수 + n번째 계단의 점수

두 가지 경우의 수 중 더 큰값이다. 

 

1)의 경우 n-1번 째의 계단을 뛰어넘었고

2)의 경우 n-2번 째의 계단을 뛰어넘었으므로 3번 연속된 계단을 밟지 않는 조건을 만족한다. 

 

 

 

[Top-down] 재귀함수 이용

public class Main {
    private static Integer[] dp;
    private static int[] step;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        step = new int[n+1];
        dp = new Integer[n+1];

        for(int i=1; i<=n; i++) {
            step[i] = Integer.parseInt(br.readLine());
        }

        dp[0] = step[0];
        dp[1] = step[1];

        System.out.println(find(n));
    }

    private static int find(int x) {
        if (dp[x] != null) return dp[x];
        if (x == 2) return dp[x] = step[1] + step[2];
        return dp[x] = Math.max(find(x - 2), find(x - 3) + step[x - 1]) + step[x];
    }
}

 

 

 

[Bottom-up] 반복문 이용

public class Main {
    private static Integer[] dp;
    private static int[] step;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        step = new int[n+1];
        dp = new Integer[n+1];

        for(int i=1; i<=n; i++) {
            step[i] = Integer.parseInt(br.readLine());
        }

        dp[0] = step[0];
        dp[1] = step[1];

        for(int i=2; i<=n; i++) {
            if (i == 2) {
                dp[i] = step[1] + step[2];
                continue;
            }
            dp[i] = Math.max(dp[i-2], dp[i-3] + step[i-1]) + step[i];
        }

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

 

 

 

 

 

<참고 자료>

https://st-lab.tistory.com/132