[BOJ11501/Java] 주식

1. 문제요약

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

11501번: 주식

나도 미래를 알면 좋겠다..

암튼 최대의 이익을 얻기 위해서는 각각의 날짜에 주식을 사야하는지, 팔아야하는지, 아니면 가만히 있어야하는지 판단해야 한다. 

 

2. 입/출력

주가는 작지만 N도 크고 특히 출력에서 부호있는 64bit 정수형으로 표현 가능하다고 했다. int는 32bit이다.. 크기에 주의하자(이거때문에 틀렸습니다 받음..)

 

3. 접근 방식

앞에서부터 나가면서 감소하는 부분이 나올 때 파는걸로 구현하려다가 생각보다 복잡한 것 같아서

뒤에서부터 살펴보는 것으로 풀이 방식을 정했다. 미래의 값보다 과거의 주식 가격이 낮다면 주식을 샀다가 미래의 날짜에 원하는 수 만큼 팔 수 있다. 오래 들고 있어도 팔 수 있으니까 주식 가격이 최대일때 한번에 파는 걸로 생각한다면

제일 미래의 주식가격을 max값으로 저장해놨다가 하루씩 앞으로 가면서 그날의 주식가격과 max 값을 비교하면서 행동을 선택하는 방식이다.

 

4. 작성한 코드

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		while(T-- > 0) {
			int N = Integer.parseInt(br.readLine());
			int[] arr = new int[N];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int i = 0; i<N; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			int max = arr[N-1];
			long profit = 0;
			for(int i = N-2; i>=0; i--) {
				if(arr[i] <= max) {
					profit += max-arr[i];
				}else {
					max = arr[i];
				}
			}
			sb.append(profit).append('\n');
		}
		System.out.println(sb);
	}

}