백만 장자 프로젝트

문제

연속된 N일 동안의 물건 매매가를 예측하여 알고 있습니다. 하루에 최대 1만큼 구입할 수 있으며, 판매는 얼마든지 할 수 있습니다. 예측된 매매가를 바탕으로 원재료를 사서 팔았을 때 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫 번째 줄에 테스트 케이스의 수 T가 주어집니다. 각 테스트 케이스의 첫 줄에는 자연수 N (2 ≤ N ≤ 1,000,000)이 주어지고, 두 번째 줄에는 N일 동안의 매매가가 공백으로 구분되어 주어집니다. (매매가는 10,000 이하)
• 출력: 각 테스트 케이스마다 #t (테스트 케이스 번호)와 함께 최대 이익을 출력합니다.

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

풀이: 역방향 탐색(Backward Traversal)을 활용한 그리디 최적화

이 문제의 핵심은 '물건을 샀을 때, 앞으로 남은 날들 중 가장 비싼 가격에 파는 것'입니다. 배열의 앞에서부터 탐색하면 현재 날짜 이후의 최댓값을 매번 다시 찾아야 하므로 시간 초과(O(N^2))가 발생하기 쉽습니다. 하지만 배열의 뒤에서부터 앞으로 탐색하면 단 한 번의 순회(O(N))만으로 완벽한 최적해를 구할 수 있습니다.

• 역방향 탐색 및 최댓값 갱신:
  • 가장 마지막 날(n - 1)의 가격을 임시 최댓값(tmp)으로 설정하고, 그 앞날(n - 2)부터 0번 인덱스까지 거꾸로 탐색합니다.
• 이익 계산 (Greedy):
  • 현재 탐색 중인 날의 가격(a[i])이 최댓값(tmp)보다 작다면, 이 날 물건을 사서 최댓값인 날에 파는 것이 이득입니다. 따라서 이익(ans)에 tmp - a[i]를 누적해 줍니다.
  • 만약 현재 가격이 최댓값보다 크다면(tmp < a[i]), 이전 날들(현재 인덱스보다 앞선 날들)에서 산 물건은 지금의 새로운 높은 가격에 파는 것이 가장 유리합니다. 따라서 새로운 최댓값으로 tmp를 갱신해 줍니다.
• 자료형 오버플로우 주의 (핵심):
  • N이 최대 1,000,000일이고 매매가가 최대 10,000이므로, 최대 이익은 대략 1,000,000 * 10,000 = 10,000,000,000 (100억)이 될 수 있습니다.
  • 이는 자바 int형의 최댓값(약 21억)을 훌쩍 넘기 때문에, 정답을 담는 변수 ans는 반드시 long 타입으로 선언하여 오버플로우를 방지해야 합니다.

코드

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            int n = Integer.parseInt(br.readLine());
            int[] a = new int[n];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }

            // 최대 이익이 int 범위를 초과할 수 있으므로 long 타입 선언
            long ans = 0;
            
            // 마지막 날의 가격을 초기 최댓값으로 설정
            int tmp = a[n - 1];
            
            // 배열의 뒤에서부터 앞으로(역방향) 탐색
            for (int i = n - 2; i >= 0; i--) {
                // 현재 가격이 최댓값보다 작으면 구매 후 판매 (이익 누적)
                if (tmp > a[i]) {
                    ans += tmp - a[i];
                } 
                // 현재 가격이 최댓값보다 크면 새로운 최댓값으로 갱신
                else if (tmp < a[i]) {
                    tmp = a[i];
                }
            }

            bw.write("#" + t + " " + ans + "\n");
        }

        bw.flush();
    }
}

알고리즘 분류

탐욕법 (Greedy Algorithm), 수학 (Mathematics)