[SW Expert Academy] 1859번 <백만 장자 프로젝트>

SW Expert Academy <백만 장자 프로젝트>

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc 

SW Expert Academy

---

백만 장자 프로젝트

원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다. 원재는 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있으며, 판매는 얼마든지 할 수 있다.

원재가 사재기해서 얻을 수 있는 최대한의 이득을 구하여라.

 

입력으로 첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스 별로 첫 줄에 자연수 N이 주어지고 그 다음 줄에 각 날의 매매가를 나타내는 N개의 자연수가 공백으로 구분되어 주어진다.

 

출력으로는 각 테스트 케이스에 대해 최대한의 이득을 구해서 출력한다.

---

문제 해결

처음에 각 매매가를 우선순위 큐에 넣어서 가장 높은 매매가를 처음에 max로 저장하고 각 매매가와 순서대로 비교해서 max보다 작다면 max에서 해당 값을 뺀 값을 누적하고 max와 같다면 우선순위 큐에서 값을 꺼내서 max를 update했다.

이렇게 하면 틀린다. 당연함 1 3 1 5 1이 매매가로 들어왔을 때, 처음에 max 값은 5가 되고 4 + 2 + 4 = 10이 되고 5를 만나서 max 값이 3으로 update 되는데 3은 이미 지나간 날이므로 제대로 문제를 풀 수 없다.

 

댓글을 보니 뒤에서부터 보는 것이 핵심이라고 해서 다시 한 번 생각해보니 할 수 있을 거 같아서 다시 풀어봤다.

max 값을 마지막 날의 매매가로 초기에 설정한다.

뒤에서부터 매매가를 보면서 max 값보다 작다면 sum에 max 값에서 해당 값을 뺀 값을 누적하고 max 값보다 크다면 max 값을 해당 값으로 update한다.

 

생각보다 간단한데 생각보다 어려웠다. ㅜ

---

코드

package SWEA1859;

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

public class Solution {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int test_case = 1; test_case <= T; test_case++) {
			int n = Integer.parseInt(br.readLine());
			String[] inArr = br.readLine().split(" ");
			long[] prices = new long[n];
			long sum = 0;
			for(int i = 0; i < n; i++) {
				prices[i] = Long.parseLong(inArr[i]);
			}
			long max = prices[n-1];
			for(int i = n-2; i >= 0; i--) {
				if(prices[i] < max) {
					sum += max - prices[i];
				}else if(prices[i] > max) {
					max = prices[i];
				}
			}
			System.out.println("#" + test_case + " " + sum);
		}

	}

}

---

결과

---

4차,,,,, 2번은 출력 형식을 지키지 않아서 틀렸는데 그것도 모르고 다른 거 고치고 있었다,,,

그래도 마지막에 알아차려서 다행이다. 출력 형식 고치니까 바로 맞았다.