[SWEA / Java] 1859번: 백만 장자 프로젝트 (D2)

문제 풀이 날짜: 2023.05.17
포스트 작성일: 2023.05.25

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

Software Expert Academy 1859번: 백만 장자 프로젝트 (D2) (문제 링크)

 

키워드

그리디

 

풀이 접근법

• 배열의 앞에서부터 뒤로 가는 게 아니라 뒤에서부터 앞으로 가면서 계산하는 발상이 필요하다.
  • 앞에서부터 계산하면 "1 2 3 4 2 6 1 1 1 1" 이란 테스트 케이스에서 반례가 생긴다. 중간에 가격이 치솟는 시점(4일)이 있더라도 6일까지 사재기 한 다음에 6일에 모두 팔아야 한다.
• 즉, 앞에서부터 사재기 하다가 값이 떨어지기 직전에 파는 것이 아니라, 맨 뒤에서부터 보았을 때 금액이 치솟는 시점마다 그 가격보다 저렴했던 전날들의 마진(maxCost - cost[i])을 모두 누적시킨다.
  • 예: 1, 1, 5, 1, 4에서는 가격이 4일 때를 기점으로 가격이 4보다 작은 날들의 마진을 구한다. 가격이 5일 때 기준으로 그 전 날들의 마진을 구한다.

 

코드

import java.util.*;

public class SWEA1859 {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();

		StringBuilder sb = new StringBuilder();
		for(int test_case = 1; test_case <= T; test_case++) {
			int N = sc.nextInt();

			int[] cost = new int[N];
			for(int i = 0; i < N; i++) { //배열에 값 할당 
				cost[i] = sc.nextInt();
			}
			
			int max = cost[N - 1];
			long result = 0;
			for(int i = N - 2; i >= 0; i--) {
				if(cost[i] < max) { //최대 금액보다 i일의 시세(cost[i])가 낮다면
					result += (max - cost[i]); //i일의 마진을 누적시킨다.
				}
				else { //최대 금액이 발견되었다면 갱신
					max = cost[i];
				}
			}
			
			sb.append("#" + test_case + " ").append(result).append('\n');
		}
		
		System.out.print(sb);
	}

}

---

역발상이 조금 필요한 그리디 문제였다. 앞에서부터 계산하면 영락없이 반례에 걸려버리는데, 이걸 고치는 과정에서 조금 헷갈려서 다른 분들의 풀이를 참고하여 코드를 작성하였다. 그리디 문제를 풀 때에는 뒤에서부터 계산하는 응용력이 필요할 것 같다. 

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week8/day4/SWEA1859.java

 

참고한 블로그 링크

https://dundung.tistory.com/119