백준 25644 - 최대 상승(자바 - 그리디)

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

25644번: 최대 상승

 

* 문제 요약

미래를 예측하는 능력을 이용해 ANA 회사의 주식 한 주를 적당한 시점에 사고 적당한 시점에 팔아서 최대한의 이득을 얻으려고 한다.

ANA 회사의 앞으로 N 일간의 주가를 a1, a2, ... aN 이라고 하자.

i 번째 날에 주식을 사고 j 번째 날에 판다면 aj - ai 만큼의 이득을 얻을 수 있다.

자금이 넉넉하기 때문에 주가가 아무리 높아도 주식을 살 수 있고, 상황이 여의치 않을 경우 사자마자 바로 팔 수도 있다.

앞으로 N 일간 ANA 회사의 주가가 주어졌을 때, 주식 한 주를 적당한 시점에 사고 적당한 시점에 팔아서 얻을 수 있는 최대 이득은 얼마일까?

 

* 입력

- 첫째 줄에 정수 N (1 <= N <= 200,000) 이 주어진다.

- 둘째 줄에 정수 a1, a2, ... aN 이 주어진다.

- ai (1 <= ai <= 10^9) 는 i 번째 날의 ANA 회사의 주가이다.

 

* 출력

ANA 회사이 주식 한 주를 적당한 시점에 사고 적당한 시점에 팔아서 얻을 수 있는 최대 이득을 출력한다.

 

* 예시 첨부

 

* 해결 과정

매 반복마다 현 시점 기준 최저가와 현재 탐색중인 주가의 차이를 구한 다음, 이전에 구했던 이득보다 더 큰지 작은지 여부에 따라 answer 변수의 값을 초기화 하는 방식으로 문제를 풀었다.

또한 최대 이득을 얻으려면 전체 주가 중에서 최대한 싼 가격에 주식을 사서 최대한 비싼 가격에 팔아주는것이 핵심이므로 매 반복마다 현재 주식의 가격이 현재 저장해놓은 최저가보다 저렴한지 아닌지에 따라 최저가 또한 계속 갱신해주는 방식으로 문제를 풀었다.

 

* 코드

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

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

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        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);
        }

        bw.write(answer + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

전체적으로 봤을 때 반드시 최적이라고 할 수는 없으나, 매 단계마다 최저가를 갱신해가며 현재 가격과 최저가의 차이를 구해서 어느정도로 이득을 보는지 계산하는 방식으로 최대 이득을 얻는 경우를 찾았다.

전체가 아닌 매 단계별로 최적의 조건을 찾았으므로 그리디 알고리즘에 해당된다.

 

또한 매 순간순간 얻을 수 있는 이득을 계산하고 이전에 얻은 이득에 비해 더 큰지 아닌지 계산하는 방식으로 작은 문제들을 해결해나가며 최대한 전체에서 얻을 수 있는 최대 이득, 즉 큰 문제 해결에 가까워지게끔 로직을 설계했으므로 다이나믹 프로그래밍 문제라고도 볼 수 있다.