SW Expert Academy <백만 장자 프로젝트>
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
백만 장자 프로젝트
원재는 연속된 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번은 출력 형식을 지키지 않아서 틀렸는데 그것도 모르고 다른 거 고치고 있었다,,,
그래도 마지막에 알아차려서 다행이다. 출력 형식 고치니까 바로 맞았다.
'Algorithm' 카테고리의 다른 글
백준 1021번 <회전하는 큐> (0) | 2022.05.16 |
---|---|
SW Expert Academy 1206번 <View> (0) | 2022.05.12 |
백준 1780번 <종이의 개수> (0) | 2022.05.10 |
백준 2504번 <괄호의 값> (0) | 2022.05.10 |
백준 17478번 <재귀함수가 뭔가요?> (0) | 2022.05.09 |
댓글