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

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&problemLevel=3&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

SW Expert Academy

 

문제

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

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

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

    1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.

    2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.

    3. 판매는 얼마든지 할 수 있다.

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

 

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

 

각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,

 

둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.

 

각 날의 매매가는 10,000이하이다.

 

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.

 

---

소스코드

import java.io.*;
import java.util.StringTokenizer;
 
class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < t; i++) {
            long result = 0;
            int n = Integer.parseInt(br.readLine());
            int arr[] = new int[n];
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }
            int max = arr[n - 1];
            for (int j = n - 2; j >= 0; j--) {
                if(max < arr[j]) max = arr[j];
                else result += (max - arr[j]);
            }
 
            sb.append("#" + (i + 1) + " " + result + "\n");
        }
 
        System.out.println(sb);
    }
}

 

해결 방법

1. 마지막날 매매가를 최대값으로 설정한다.
2. 매일의 매매가를 현재까지의 최대값과 비교하면서, 현재 최대값보다 i번째 날의 매매가가 높으면 최대값을 해당 매매가로 갱신하는 로직을 하루씩 거슬러오며 실행한다.
3. i번째 날의 매매가가 현재 최대값보다 작을 경우, 최대값과 i번째 날 매매가의 차이를 계산하여 이익으로 간주하고 총 이익에 더해준다.