[BOJ] 백준 11501 - 주식 풀이

1. 문제

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

11501번: 주식

2. 풀이

• 문제에서 주어진 행동은 총 3가지이다.
  1. 주식 하나를 산다.
  2. 원하는 만큼 주식을 판매한다.
  3. 아무것도 하지 않는다.
• 이 문제를 틀리는 대부분의 경우는 그리디적인 접근을 해서 틀리는 경우일 것이다.
• 그리디적인 접근 방법은 주가의 최대치에서 다음날 떨어진다면 현재 날짜에 기존에 구입했던 주식을 판매하는 것이다.
• 그러나 이는 최대 이익을 볼 수 있는 방법이 아니다.
• 올바른 방법은 주가가 떨어지는 시점이 아니라, 오늘 산 주식을 오늘 이후 가장 비싸게 팔 수 있는 날에 판매하는 것이다.
• 즉 가장 비싸게 팔 수 있는 날까지 주식을 계속 사야 한다.
• 이를 앞에서부터 계산하면 주식을 판 다음날 부터 다시 최댓값을 구하는 방식으로 구현해야 하지만, 뒤에서부터 계산한다면 가장 비쌀 때의 가격을 쉽게 찾을 수 있으므로 비교적 간단하게 구현할 수 있다.
  
  
• 날짜를 거꾸로 탐색하면 최대 주가를 바로바로 갱신할 수 있다.
• 이 때 갱신이 가능하다는 건 지금까지 주가보다 오늘 주가가 비싸다는 것이므로 최대 주가를 갱신하면 된다.
• 갱신이 안 된다는 건 오늘 산 주가를 지금까지 갱신한 최대 주가날에 파는게 최대 이익이라는 것이므로 이익을 계산한다.
• 그리디는 정말 생각하기 어려운 것 같다..
  
  
  
  

3. 소스코드

import java.io.*;
import java.nio.channels.GatheringByteChannel;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	// 다음날 주가가 오늘 주가보다 떨어질 때 판다 -> X (원래 생각)
	// 오늘 이후 최대 이익을 낼 수 있는 날에 판다 -> 뒤에서부터 본다.
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());
		for (int i = 1; i <= T; i++) {
			int N = Integer.parseInt(br.readLine()); // 주식의 수
			int[] arr = new int[N];
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				arr[j] = Integer.parseInt(st.nextToken());
			}
			
			long max = 0; // 현재까지 가장 비싼 주가
			long result = 0; // 최대 이익
			
			int length = arr.length - 1;
			
			for (int j = length; j >= 0; j--) {
				// 현재 최고 주가보다 큰 주가를 만난다면
				if (max < arr[j]) {
					max = arr[j]; // 주가 갱신
				} 
				
				// 현재 주가가 작거나 크다는 것은 오늘이 가장 비싸게 팔 수 있는 날이다.
				else {
					result += max - arr[j];
				}
			}
			
			bw.write(Long.toString(result) + "\n");
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
}

4. 점수

60 / 100