25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.
다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.
다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.
1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
3. 판매는 얼마든지 할 수 있다.예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.
[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,
둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.
각 날의 매매가는 10,000이하이다.
[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.
[예제 풀이]
1번째 케이스는 아무 것도 사지 않는 것이 최대 이익이다.
2번째 케이스는 1,2일에 각각 한 개씩 사서 세 번째 날에 두 개를 팔면 10의 이익을 얻을 수 있다.
입력
3
3
10 7 6
3
3 5 9
5
1 1 3 1 2
출력
#1 0
#2 10
#3 5
package prc_d2;
import java.io.*;
public class P1859 { // 백만장자프로젝트
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(reader.readLine());// testcase
StringBuilder sb = new StringBuilder();
for (int k = 1; k <= tc; k++) {
int n = Integer.parseInt(reader.readLine());// n일만큼의 매매가
int[] a = new int[n]; // 입력받은 n의 크기만큼의 배열a를 선언해준다
String[] arr = reader.readLine().split(" ");
// 마지막날까지의 매매가를 공백을 기준으로 잘라 배열 arr에 저장해준다
for (int i = 0; i < n; i++) {F
a[i] = Integer.parseInt(arr[i]);
// arr 순서대로 저장한것 => a에 저장
}
int max = a[n - 1];
// 최고가를 a의 마지막자리에 두기위해 max를 선언
long ans = 0;
for (int i = n - 2; i >= 0; i--) {
// a[n-2]의 자리부터 0까지 반복문을 돌리면서
if (max > a[i]) {
// 최대 매매가보다 a[i]의 매매가가 작다면
ans += max - a[i];
// 최대 매매가 - a[i]의 값을 계속해서 더해주고
} else {
// 최대 매매가보다 a[i]의 매매가가 크다면
max = a[i];
// 최대매매가를 a[i]로 초기화해준다.
}
}
sb.append("#" + k + " " + ans + "\n");
}
System.out.println(sb.toString());
}
}
