[실버3, DP] 백준 2579 - 계단 오르기 (자바)

Think

1. 하 DP.... 정말 어렵다 문제에 주어진 조건을 성립하면서 DP로 푸려는 아이디어가 어려웠다.

2. https://st-lab.tistory.com/132 를 참고했다.

 

제출 코드 (Top-down)

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

public class test {
    static int n;
    static int sequence[];
    static Integer dp[];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

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

        progress();
    }

    private static void progress() {

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

    private static int recursion(int number) {

        if(dp[number] == null){
            dp[number] = Math.max(recursion(number-2), recursion(number-3) + sequence[number - 1]) + sequence[number];
        }

        return dp[number];
    }

    private static void init() throws IOException {
        n = Integer.parseInt(br.readLine());

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

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

        dp[0] = 0;
        dp[1] = sequence[1];

        if(n>=2){
            dp[2] = sequence[1] + sequence[2];
        }
    }

}

 

 

제출코드 2 (bottom-up)

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

public class test {
    static int n;
    static int sequence[];
    static Integer dp[];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

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

        progress();
    }

    private static void progress() {

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

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

    }

    private static void init() throws IOException {
        n = Integer.parseInt(br.readLine());

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

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

        dp[0] = 0;
        dp[1] = sequence[1];

        if(n>=2){
            dp[2] = sequence[1] + sequence[2];
        }
    }

}