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

문제

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

SW Expert Academy

 

문제 이해하기

예시를 보면서 문제를 이해해보자.
 
세 번째 테스트 케이스를 보면
1 1 3 1 2
 
(buy buy sell) (buy sell)
(-1 -1 + (3 * 2)) + (-1 + (2 *1))
 
첫 번째 판매는 3일차에, 두 번째 판매는 5일차에 이루어진다.
(*조건 3.판매는 얼마든지 할 수 있다.)
 
당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있으므로
(*조건 2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.)
 
최댓값이 보이기 전까지 물건을 하루에 하나씩 죄다 쟁여놨다가 최고점에 판다.
 
즉, 맨 뒤부터 최댓값을 찾으면서
(*조건 1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.)
 
최댓값이 갱신되기 전까지 물건을 모두 구매하여 최고점에 판 값을 구한다.
 
 
 

코드 구현

input.txt

3 // 첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
3 // Test Case 1 : 자연수 N
10 7 6 // 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.
3 // Test Case 2 : 자연수 N
3 5 9 // 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.
5 // Test Case 3 : 자연수 N
1 1 3 1 2 // 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.

 
 

Pseudo-code

 

int T; // 테스트 케이스의 개수

/* tc만큼 for문 */
	int N; // i번째 테스트 케이스 첫 번째 줄(자연수 N)
    int[] arr = new int[N]; // 각 날의 매매가를 나타내는 N개의 자연수들을 담을 배열
    
    /* 파싱해서 배열에 담기 */
    
    long MAX = Long.MIN_VALUE; // 갱신할 최댓값
    int num; // 사재기한 물건의 개수
    long cost; // 물건을 사는 데 들어간 비용
    long result; // 총 판매 수익
    
    /* 배열의 마지막 인덱스부터 0까지 for문 */
    	if(최댓값 발견 > 판매 수익 업데이트 > 최댓값 갱신 > 비용과 사재기한 물건 개수 초기화)
        else(들어간 비용 업데이트 > 사재기한 물건 개수 업데이트)
        
    (for문 끝나고 난 후엔 마지막 판매 수익이 업데이트되지 않음.)
    판매 수익 업데이트
    
    테스트 케이스의 결과 출력

 
 

Code

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

class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수

        /* tc만큼 for문 */
        for(int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine()); // i번째 테스트 케이스 자연수 N
            int[] arr = new int[N]; // 각 날의 매매가를 나타내는 N개의 자연수들을 담을 배열

            String str = br.readLine();
            StringTokenizer st = new StringTokenizer(str, " "); // 공백 기준으로 파싱

            // 파싱한 값 배열에 담기
            for(int j = 0; st.hasMoreTokens(); j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }

            long max = Long.MIN_VALUE; // 갱신할 최댓값
            int num = 0; // 사재기한 물건의 개수
            long cost = 0L; // 물건을 사는 데 들어간 비용
            long result = 0L; // 총 판매 수익

            for(int k = N - 1; k >= 0; k--) {
                if(arr[k] > max) {
                    // 최댓값 발견
                    result += (max * num - cost); // 판매 수익 업데이트
                    max = arr[k]; // 최댓값 갱신
                    cost = 0; // 비용 초기화
                    num = 0; // 사재기한 물건 개수 초기화
                } else {
                    cost += arr[k]; // 들어간 비용 업데이트
                    num++; // 사재기한 물건 개수 업데이트
                }
            }

            // for문 끝나고 난 후엔 마지막 판매 수익이 업데이트되지 않음.
            result += (max * num - cost); // 판매 수익 업데이트

            System.out.println("#" + (i + 1) + " " + result);
        }
    }
}