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

문제: 1859. 백만 장자 프로젝트
날짜: 08/28 (수)
성공여부: O(댓글힌트)

 

그리디 문제이다. 그리디에 대한 준비가 안되어있어서 좀 어려웠다. 결론부터 말하면 배열을 뒤로 반복해서 풀면 풀리는 문제이다. 무조건 배열을 앞에서부터 반복할 필요가 없다는 생각을 해야한다.. 이게 참 쉬운데 어려운듯하다.

 

처음 풀이는 앞에서부터 반복하면서 현재 값에서 바로 뒤에 자기보다 작은 값이 나오면 현재 값을 기준으로 지금까지 산 물건들을 팔아 그 차액을 ret 변수에 더했다. 예제만 놓고보면 해당 로직에 문제가 없다. 그런데 아래 반례가 있다.

1 2 3 5 2 4 7 1

1 2 3 5 2 4까지 모두 산다음에 7에서 팔면 최대 이익!
그러나, 위의 로직대로 한다면 1 2 3 까지 산 후 5에서 모두 팔고, 다시 2 4까지 산 후 7에서 판매한다.

 

이런 반례를 생각못해서 댓글을 참고했고 뒤에서 풀면 된다고 해서 그 생각을 갖고 다시 풀었다.

 

배열의 뒤에서부터 배열의 원소를 가지고 max 값을 갱신하면서 max 값보다 작은 값들은 사놓고 max에서 판매하면 그때가 제일 이득을 볼 수있는 상황이니까 그 차액을 계산해 ret에 더해준다. 위의 예제를 예로 들면

1 2 3 5 2 4 7 1
처음에 max = 1

그리고 다음 원소로 가면 max < 7 이기 때문에 max = 7이 되고
이후부터는 계속 max > 4 or 2 or 5 or 3 or 2 or 1이다.
그럼 max 값에 해당 원소를 빼서 그 차액을 계속 ret에 더해주면 된다.

 

 

코드

import java.util.Scanner;

public class Solution {

    static int[] gold;
    static long ret;

    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();

            gold = new int[n];
            for (int i = 0; i < n; i++) gold[i] = sc.nextInt();

            ret = 0;
            int max = 0;
            for (int i = n-1; i >= 0; i--) {
                if (gold[i] > max) max = gold[i];
                else ret += (max - gold[i]);
            }

            System.out.println("#" + test_case + " " + ret);
        }
    }
}