[자바] 백준 25644 - 최대 상승 (java)

 문제 : boj25644

---

 

필요 알고리즘 개념

• 그리디
  
  • 매번 입력 중 최소값과, '현재값-최소값'의 최대값을 갱신하면서 모든 경우를 보면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  이 문제를 풀 때 주의할점이, 문제의 조건이 '주식 한 주를 적당한 시점에 사고 적당한 시점에 팔아서 얻을 수 있는 최대 이득' 이므로 딱 한번만 주식을 사야 한다는 점이다. 즉 입력이 '1 5 2 6' 일 경우 1에사고 5에 팔아서 4의 이득을 얻고, 2에 사고 6에 팔아 또 4의 이득을 얻어 8을 이득보는게 답이 아니고, 1에서 사고 6에 팔아 5의 이득을 내는게 이 문제에서 원하는 최대 이득이다. 

 

  그렇다면 알아야하는건 다음과 같다.

1. 현재 i번째 날의 주가를 보고 있을 때, i 이하의 날 중 최소 주가 값

-> 1번째 날부터 차례대로 입력받으면서 최소값을 갱신해주면 매번 i번째날 이하의 최소 주가값을 구할 수 있다.

2. i번째날의 주가 - '1'에서 얻은 최소값이 현재까지 구한 최대이득보다 크다면 갱신한다.

 

---

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int answer = 0;
        int min = Integer.MAX_VALUE;
        while (n-->0) {
            int cur = Integer.parseInt(st.nextToken());
            answer = Math.max(answer, cur - min);
            min = Math.min(min, cur);
        }
        System.out.println(answer);
    }

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