[swea/java] 1859. 백만 장자 프로젝트(D2)

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.

다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.

다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.

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

예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.

 

 

며칠의 매매가를 알 수 있는지 주어지기에 배열로 풀면 되겠다는 생각이 들었습니다.

 

하여 

1. 테스트 케이스 다음으로 들어오는 입력값을 배열의 크기로 잡고

2. 가장 마지막 날부터 진행했습니다.

3. 가장 마지막 날의 값을 최댓값으로 지정하고

3-1. 그 전 날의 값과 최댓값을 비교

3-1-1. 최댓값이 더 크다면 팔아서 이익을 남기고

3-1-2. 최댓값이 작다면 전 날의 값을 최댓값으로 변경해주었습니다.

 

import java.util.*;

public class Solution {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for(int t = 1; t<=T; t++) {
			long profit = 0;
			int size= sc.nextInt();
			int max = 0;
			int[] info = new int[size];
			
			for(int i = 0 ; i <size;i++) {
				info[i] = sc.nextInt(); //배열에 값 집어넣기
			}
			
			max = info[size-1]; //마지막 날을 최대값으로 지정
			for(int i =size-1;i>0;i--) {
				if(info[i-1] < max) {
					//마지막 날의 값이 최댓값이 맞을 시 팔아서 이익 실현
					profit += (max - info[i-1]);
				}else {
					//최댓값 새로 지정
					max = info[i-1];
				}
			}
			System.out.println("#" +t + " " + profit);
		}
	}

}

 

 

주의할 점은 이익 변수 선언 시 int 가 아닌 long으로 해야 한다는 점인데요,

문제에서 '각 날의 매매가는 10,000이하' 라고 언급하는 만큼 이익이 int가 담을 수 있는 최댓값을 뛰어 넘는 테스크 케이스가 나올 수 있기 때문입니다.