[백준] 11501번 : 주식

문제

 

 

접근 방식

싼 값에 주식을 사고 비싼 값에 팔면 가장 이득을 볼 수 있다는 당연한 사실을 통해

주어진 주가를 역으로 탐색해 현재 가장 큰 값보다 비싼 값을 만날 때까지

이전의 모든 주식을 산 후에 팔아주면 된다.

3 2 4 5 7 8 6 9 8 4 5

 

예를 들어 위와 같이 주가 목록이 주어졌을 때 역으로 탐색하면

 

5를 기준으로 더 큰 값인 8을 만나기 전까지 주식을 사면

4원에 주식을 산 후에 5원에 팔아서 1원 이득을 볼 수 있고

 

다시 8을 기준으로 더 큰 값이 9를 만나기 전까지는

어떠한 주식도 살 수 없기 때문에 8을 그대로 팔아 0원 이득을 볼 수 있으며

 

다시 9를 기준으로 더 큰 값이 없으므로 남은 모든 주식을 사면

(9원 * 7일) - (3 + 2 + 4 + 5 + 7 + 8 + 6) = 63 - 35 = 28

 

28원 만큼의 이득을 볼 수 있다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine());
		int n;
		int[] arr;

		while (t-- > 0) {
			n = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			arr = new int[n];

			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}

			long profit = 0;
			long max = 0;
			long sum = 0;
			long count = 0;

			for (int i = n - 1; i >= 0; i--) {
				long price = arr[i];

				if (max == 0) {
					max = price;
					continue;
				}

				if (i == 0) {
					if (price <= max) {
						count++;
						sum += price;
					}
					profit += (count * max - sum);
					continue;
				}

				if (max >= price) {
					count++;
					sum += price;
				} else {
					profit += (count * max - sum);
					count = 0;
					sum = 0;
					max = price;
				}
			}

			sb.append(profit).append("\n");
		}

		System.out.println(sb);
	}
}