SWEA 1859 - 백만 장자 프로젝트 ( JAVA )

SW Expert Academy

 

출처 - SW Expert Academy

---

알고리즘

매매가가 가장 높을 때 팔아야 큰 이익을 얻을 수 있다. 

 

주어진 물건들을 구매하다가 매매가가 최고가일 때 팔면서, 해당 과정을 주어진 물건만큼 반복한다. 

 

ex ) 

예제에 1 1 3 1 2 를 보면 ,

1. max = 3 이기 때문에, [1 ,1] 구매 후 [3] 일 때 팔면 2 + 2 = 4 의 이익을 볼 수 있다.

2. 남은 물건 들 중 max =2 이기 때문에 , [1] 구매 후 [2] 일 때 팔면 1 의 이익을 볼 수 있다. 

3. 총, 4+1 = 5 의 이익을 얻을 수 있다. 

 

예제에 10 7 6 을 보면 , 

1. max = 10 이고 가장 첫날의 물건이기 때문에 살 것이 없다. 

2. 남은 물건 들 중 max = 7이고, 살 것이 없다.

3. 남은 물건 들 중 max = 6이고, 살 것이 없다. 

 

 

 + 신경 써야 할 부분 

물건의 갯수 N이 최대 100만개 까지 주어지고, 매매가가 10,000 이하 이기 때문에 최대 이익이 20억을 넘을 경우가 생길 수 있다. 최대 이익을 저장할 변수를 int 형으로 하면 overflow가 발생할 수 있기 때문에 long형으로 ~ 

 

---

 

소스 코드

import java.util.*;
import java.io.*;

public class Solution_SWEA_1859_D2 {
	public static void main(String[] args) throws Exception{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine()); //테스트케이스
		for(int tc=1; tc<=T; tc++) {
			int N= Integer.parseInt(br.readLine()); 
			int[] pay = new int[N];
			StringTokenizer st= new StringTokenizer(br.readLine(), " ");
			for(int i=0; i<N; i++) {
				pay[i] = Integer.parseInt(st.nextToken());
	
			}
			
			long sum=0; // 최대 이익 ( int > overflow 발생 가능 ) 
			
			int start_index=0;
			int max_index=0; //매매가 최댓값의 index 
			
			while(start_index < N) {
				int max= Integer.MIN_VALUE; 
				// 현재 값들 중 최댓값 찾기 
				for(int i=start_index; i<N; i++) {
					if(max < pay[i]) {
						max = pay[i]; 
						max_index=i;
					}
				}
				
				for(int i=start_index; i<max_index; i++) {
					sum += (max-pay[i]); 
				}
				start_index = max_index+1; //남은 물건 들 중 탐색 시작 
				
			} // end of while 
			
			System.out.println("#"+tc+" "+sum);
		}// end of testcase for 
	}
}