SWEA 1859 백만 장자 프로젝트(그리디) ★★

SW Expert Academy

물건의 매매가를 하루하루 순차적으로 봐야하기 때문에 정렬을 하지않고 O(N)으로 판단해야 하는 문제임을 파악했다.

 

처음에는 O(N^2)으로 기준을 하나 잡고 기준뒤에 있는 가장 큰 수를 찾은다음 매매를 하는 방식으로 최댓값을 구했지만 당연히 시간초과가 났다(N의 범위 : 1,000,000)

 

다음 방법으로 DP를 생각해봤다. dp[i]가 i번째 날에 얻을 수 있는 최댓값으로 정의를 했는데 i번째 날 가지고 있는 물건을 다 팔아야 dp가 최댓값이 될텐데 안팔고 나중에 더 큰수가 나타날 때 파는 경우가 생기기 때문에 dp값이 계속 바뀌므로 DP도 아니였다.

 

따라서, 정렬도 아니고 완전탐색도 아니고 DP도 아니기때문에 그리디라고 결론을 내렸으며 O(N)으로 1번 탐색할 때 내가 가지고 있는 물건들을 가장 최댓값을 만날 때 팔아야한다는 건데 temp변수를 하나 만들어서 판단하는건가?

 

10 7 6 처럼 현재값이 다음값보다 작아지면 굳이 현재 물건을 살 필요가 없다는건 알겠다.

 

하지만 1 2 4 3 1 2 5 처럼 4 이후에 4보다 더 큰 값이 나올 수 있는데 섣불리 그냥 큰 값을 만났다고 물건을 파는건 잘못된 방식이다.

 

나는 이걸 모르기때문에 물건을 미리 사두고 현재 사왔던 물건들의 최댓값보다 더 큰값을 만났다면 그 때 파는경우 안파는 경우 2가지의 경우를 나누어서 고려하는 방식인가? 라고 생각해봤는데 그렇게되면 트리구조로 그려보게 되면 분기가 엄청 많이 생기기 때문에 이 방법도 아닌거 같고...

 

현재 사왔던 물건들의 최댓값보다 더 큰값을 만났다고 하더라고 그 값이 배열의 최댓값이라는 보장이 없기 때문에 어떻게 풀어나갈지 매우 고민이다...

 

해결방법

지금 고민이였던게 앞에서부터 탐색해서 어떤값이 최댓값인지 모르는 상황이였기 때문에 문제가 발생했었는데 그럼 배열을 뒤부터 탐색하면 되지 않을까?

 

배열을 뒤부터 탐색한다는 이 생각하나만 했으면 너무 쉽게 풀었을 문제인데 아쉬움이 많이 남은 문제였다

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


public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int T = Integer.parseInt(st.nextToken());
        for (int tc = 1; tc < T+1; tc++) {
            int N = Integer.parseInt(br.readLine());
            int[] data = new int[N];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                data[i] = Integer.parseInt(st.nextToken());
            }
            long res = 0;

            int std = data[N-1];

            for (int i = N-1; i >= 0; i--) {
                if (std >= data[i])
                    res += std - data[i];
                else
                    std = data[i];
            }
            System.out.println("#"+tc+" "+res);
        }


    }
}