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

---

문제 요약

연속된 날의 매매가가 주어졌을 때, 최대 이익으로 나올 수 있는 값을 구하시오.

< 예시 >

[ 입력 ]

3	// T : 테스트 케이스 수
3
10 7 6
3
3 5 9
5
1 1 3 1 2

[ 출력 ]

#1 0
#2 10
#3 5

< 제약 조건 >

• 하루에 최대 1개만 구매가능하며, 판매는 얼마든지 팔아도 상관없다.
• 2 ≤ N ≤ 1,000,000
  • 각 날의 매매가를 나타내는 N개의 자연수
• 각 날의 매매가는 10,000 이하이다.

< 백준 >

• 골드 D2
• 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc

---

풀이

• 각 날의 개수가 최대 1,000,000이고, 매매가 또한 최대 10,000이므로 계산 값은 최악의 경우 100억을 넘게 된다. 따라서, 일부 변수는 long으로 선언하자.

(1) 현재 매매가가 최대 매매가(max)보다 작다면, max - 현재 매매가를 통해 얻을 수 있는 수익을 계산한다.
(2) 만일 현재 매매가가 최대 매매가보다 크다면, 최대 매매가를 갱신한다.

---

Code

import java.io.*;
import java.util.Scanner;

public class SWEA1859 {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("SWEA/static/input.txt"));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Scanner sc = new Scanner(System.in);
        int testcase = sc.nextInt();
        for(int t = 1; t <= testcase; t++) {
            int N = sc.nextInt();
            int[] list = new int[N];
            for(int i=0;i<N;i++) {
                list[i] = sc.nextInt();
            }
            bw.write("#"+t+" ");
            long result = solve(N, list);
            bw.write(result + "\n");
        }
        bw.flush();
    }

    private static long solve(int N, int[] list) {
        long total = 0;
        long max = Long.MIN_VALUE;
        for(int i=list.length-1;i>=0;i--) {
            // 구매
            if (list[i] <= max) {
                total += (max - list[i]);
            }
            // 판매
            else {
                max = list[i];
            }
        }
        return total;

    }
}

---

후기

느낀점

앞에서부터 계산한 코드에선 테스트 케이스 2개만 통과하였다. 확실히 뒤에서부터 계산하니 코드도 깔끔하고 효율적이다. 탐색, 비교 문제에선 항상 뒤에서부터 계산하면 어떨까하는 생각을 기본 갖고 있어야겠다.