1. 문제
https://www.acmicpc.net/problem/11501
11501번: 주식
입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타
www.acmicpc.net
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
