[SWEA] 1859. 백만장자 프로젝트

SWEA D2 1859 백만장자 프로젝트

 

 

문제링크

SW Expert Academy

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/-PrR0MhfX6Y

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2022. 2. 23.
 * @see 
 * @performance 139,036 kb, 430 ms
 * @category #
 * @memo
 */

public class SWEA_D2_1859_백만장자프로젝트{
    
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens;
    
    static int T;
    static int N;
    static int [] map;
    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        T = Integer.parseInt(input.readLine());
        for(int t=1; t<=T; t++) {
            N = Integer.parseInt(input.readLine());
            map = new int[N];
            
            tokens = new StringTokenizer(input.readLine());
            for(int i=0; i<N; i++) {
                map[i] = Integer.parseInt(tokens.nextToken());
            }
            //System.out.println(Arrays.toString(map));
            
            // N: 백만, 금액: 10000 --> 천억!!
            long profit = 0;
            
            // 뒤에서 부터 생각해보자~~~ -> 최대값에서 작은 값을 계속 빼주는 구조.
            int max = 0;
            for(int i=N-1; i>=0; i--) {
                // 내 뒤로 최대가 있다면 --> 모조건 구매, 이때의 이익은  최대 - 오늘 금액
                int today = map[i];
                if(max > today) {
                    profit +=max - today;
                }
                // 오늘이 더 최대인 상황 --> 최대값 갱신
                else {
                    max = today;
                }
            }
            output.append(String.format("#%d %d%n", t, profit));
        }
        System.out.println(output);
    }
    // REMOVE_START
    private     static String src = "3\n"
            + "3\n"
            + "10 7 6\n"
            + "3\n"
            + "3 5 9\n"
            + "5\n"
            + "1 1 3 1 2";
    // REMOVE_END
    
}