SWEA 1859 백만 장자 프로젝트

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
	public static void main(String args[]) throws Exception
	{

		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();

		for(int test_case = 1; test_case <= T; test_case++)
		{
            int N = sc.nextInt();
            int[] arr = new int[N];
            for(int i =0; i<N; i++){
                arr[i] = sc.nextInt();
            }
            
            long answer = 0;
            long sum = 0;
            int count = 0;
            int max = 0;
            boolean flag = false;
            for(int i = 0; i<N; i++){
               if(!flag){
                   for(int j = i+1; j<N; j++){
                   		max = Math.max(max,arr[j]);
              	   }
               }
               
               if(arr[i]>=max){
                   answer += arr[i]*count - sum;
                   count = 0;
                   max  = 0;
                   sum = 0;
                   flag = false;
               }
               else{
                   sum += arr[i];
                   count++;
                   flag = true;
               }
            }
                System.out.println("#" +test_case+" "+answer);

		}
	}
}

풀이방법

1. 다음날부터의 매매가의 최대를 구한다.
2. 오늘이 미래의 매매가의 최대값보다 작다면, sum에 오늘 매매가를 저장하고, count를 증가시킨다.
3. 오늘이 미래의 매매가의 최대값보다 크다면, 물건을 판다.
   그 동안 저장해놓은 오늘 매매가 * count값에서 그 동안 저장해놓은 sum값을 빼주고, sum,count,max값을 0으로 초기화 시킨다.
4. 매일 미래의 최대값을 구할 필요없이 물건을 판뒤에만, 구해주면되기 때문에 시간복잡도를 줄이기 위해 flag를 사용한다.

후기

단순한 구현문제인데 뭔가 생각해내기 어려웠다.
그리고 출력값이 크기때문에 long타입을 사용해야 한다.