[백준][java] 25644 - 최대 상승

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

25644번: 최대 상승

난이도 : S5

유형 : 그리디, DP

시간 : N ( N <= 200_000)

---

문제 풀이

그리디와 DP로 쉽게 풀리는 문제이다.

하지만 이 문제는 그리디가 더 최적화인 문제이다.

 

입력값을 하나씩 처리할 때마다 현재 입력값과 이전의 최소 입력값의 차를 정답의 최댓값으로 갱신하고

입력값의 최소값을 갱신해 나가면 된다.

 

[그리디]

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

/*author : DDing77*/

public class Main {

    private int N;
    private int min;
    private int res;

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        min = Integer.MAX_VALUE;
        res = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int cur = Integer.parseInt(st.nextToken());

            res = Math.max(res, cur - min);
            min = Math.min(min, cur);
        }

        System.out.println(res);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

 

[DP]

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

/*author : DDing77*/

public class Main {

    private int N;
    private int[][] dp;

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        dp = new int[N][2];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int cur = Integer.parseInt(st.nextToken());

            if (i == 0) {
                dp[i][0] = 0;
                dp[i][1] = cur;
                continue;
            }

            dp[i][0] = Math.max(dp[i - 1][0], cur - dp[i - 1][1]);
            dp[i][1] = Math.min(dp[i - 1][1], cur);
        }

        System.out.println(dp[N - 1][0]);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}