SWEA 1859. 백만 장자 프로젝트 :: 돼지개발자

SWEA 1859. 백만 장자 프로젝트 

(https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc)

---

"완전 탐색할 건 아니야, 뭔가 아이디어를 찾자."

해당 문제에서 N이 1,000,000 까지가 있고, 각 지점에서 할 수 있는 행동은 산다/판다/아무것도 안한다. 의 세가지로 나뉜다. 따라서 대략적인 시간복잡도를 계산해 보면 3^1,000,000 이 되고, 완전 탐색으로는 시간 내에 풀 수 없다. 따라서 다른 아이디어를 찾아야 했다.

주식 그래프를 생각해보자. 언제 파는 것이 이익이 최대가 될까? 당연히 고점 보다 낮게 사서 고점에 파는것이 좋다. 고점을 그래프의 가장 끝점으로 우선 잡는다.

내가 찾은 고점 보다 크거나 같으면 ? 새로운 고점이네. 갱신한다.

내가 찾은 고점 보다 작다면 ? 이익이 생길 수 있겠네. 해당 지점에서 산걸 고점에 팔자.

사실 위에 과정을 잘 구현하지 못했다 ㅠ 머리로는 생각이 됐는데 ..ㅎㅎㅎㅎㅎ 암튼 결과값은 1,000,00 * 10,000 으로 int형 범위를 넘어가므로 long 형으로 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int T, N;
    static int[] price;
    static long result;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        T = Integer.parseInt(br.readLine());
        
        int t = 1;
        while(T-- > 0) {
            N = Integer.parseInt(br.readLine());
            result = 0;
            price = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                price[i] = Integer.parseInt(st.nextToken());
            }
            int point = price.length-1;
            
            for (int i = price.length-1; i >= 0; i--) {
                if(price[i] < price[point]) {
                    result += price[point]-price[i];
                }
                else {
                    point = i;
                }
            }
            System.out.printf("#%d %d%n",t++,result);
        }
    }
 
}