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

문제

다음과 같은 조건 하에서 사재기를 하여 최대한의 이득 구하기 

    1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
    2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
    3. 판매는 얼마든지 할 수 있다.

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

 

입출력 예

 

 

풀이

해당 문제는 주어진 판매가 배열의 마지막 원소에서부터 풀면 된다. 

 

구매한 가격보다 판매가가 최고로 큰 경우에만 팔아야 하기 때문이다. 

따라서 아래와 같은 방식으로 움직인다. 

1. 마지막 원소를 가장 큰 수라고 가정한다. 
2. 마지막 원소와 하나 앞의 원소의 크기를 비교 한다. 
    2-1. 마지막 원소가 클 경우 >> 하나 앞의 원소를 구매한다. (이득 += 가장 큰 수 - 구매할 원소의 크기)
    2-2. 마지막 원소가 작은 경우 >> 가장 큰수 값을 하나 앞의 원소로 지정한다. 

3. 2번의 과정을 주어진 배열이 끝날때까지 반복한다. 

 

 

1 1 3 1 2 이라고 주어졌다고 가정해보자 

마지막부터라고 생각하면 2 1 3 1 1이 된다. 

 

1. 2를 max 값으로 설정

2. 1이 max 2보다 더 작기에 1 구매 (2-1) 

>> sum += 2-1 

>> sum = 1 

 

3. 3이 max 2보다 크기에 max = 3 (2-2)

4. 1이 max 3보다 작기에 1 구매 (2-1)

>> sum += 3-1

>> sum = 1+2 = 3

 

5. 1이 max 3보다 작기에 1 구매 (2-1)

>> sum += 3-1

>> sum = 3+2 = 5

 

따라서 최대 이익은 5가 된다. 

 

이렇게 뒤에서부터 살펴보게되면 남은 날 중 가장 큰 값을 쉽게 찾을 수 있게 된다. 

 

 

코드

첫번째 for문 : 배열을 거꾸로 저장

두번째 for문 : 2번 로직 

println           : 최대 이익 출력 

Scanner sc = new Scanner(System.in);

        int tc;

        tc = sc.nextInt();

        for (int i = 0; i < tc; i++) {

            int[] num = new int[sc.nextInt()];

            for (int k = num.length - 1; k >= 0; k--) {

                num[k] = sc.nextInt();

            }

            long sum = 0, max = 0;

            for (int j : num) {

                if (max < j) {

                    max = j;

                }

                if (j < max) {

                    sum += max - j;

                } else

                    continue;

            }

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

        }

 

SWEA 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc

SW Expert Academy