[BOJ] 11501: 주식 (JAVA)

문제

https://www.acmicpc.net/problem/11501

 

여담

SWEA에서 풀었던 백만 장자 프로젝트랑 거의 같은 문제인 것 같다. 그치만 기억하는 풀이 방법이 확실하지 않아서 풀이를 참고했다..ㅎ

 

요즘 들어 느끼는데 안 좋은 습관이 있는 것 같다. 이미 풀었던 문제는 풀이를 약간 기억하고 있는 경우가 많아서 그 기억을 기반으로 문제를 풀려고 한다. 또 "이미 풀었던 문제인데도 못 풀어..??" 라는 생각 때문에 비교적 빨리 풀이를 보고 문제를 푸는 것 같다. 이미 풀었던 문제라도 그 풀이를 도출하는 과정이 중요한 것이니까 제발 기억을 기반으로 풀지 말고 생각을 하고 풀자!

 

ps. 그리디는 진짜 어려운 것 같다. 많이 풀어보고 이미 풀었던 문제도 다시 풀어보는 것이 정답인 듯.. 

 

풀이

주식을 구입한 가격과 주식을 판매하는 가격의 차이가 클수록 주식에서 최대 이익을 얻을 수 있다. 따라서 역방향으로 탐색을 하면서 주식의 가격이 가장 높을 때를 기록한다. 현재 주식의 가격이 최고 가격보다 낮으면 주식을 구매하고, 그렇지 않으면 최고 가격을 갱신(= 아무것도 하지 않는 것)하면 된다. 

 

주식의 가격이 1 1 3 1 2라면 다음과 같이 행동할 때 최대 이익을 얻을 수 있다.

• 첫째 날과 둘째 날에 주식을 구매하고 셋째 날에 주식을 판매하기 ((3 - 1) + (3 - 1) = 4)
• 넷째 날에 주식을 구매하고 다섯 째 날에 주식을 판매하기 (2 - 1 = 1)
• 따라서 최대 이익은 5 (4 + 1)이 된다.

 

즉, 정리하면 다음과 같다.

• 주식의 최대 가격 > 현재 주식의 가격
  • 주식 구매하기
  • total += max - arr[i]
• 주식의 최대 가격 ≤ 현재 주식의 가격
  • 주식의 최대 가격 갱신하기(= 아무것도 하지 않기)
  • max = arr[i]

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());
            int[] arr = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            int max = arr[N - 1];
            long total = 0L;
            for (int i = N - 2; i >= 0; i--) {
                if (arr[i] < max) { // 주가가 가장 높을 때보다 낮은 가격인 경우라면
                    // 주식 사기
                    total += max - arr[i];
                } else { // 주가가 가장 높을 때보다 더 높은 가격인 경우라면
                    // 최고 주가 갱신하기
                    max = arr[i];
                }
            }
            sb.append(total).append("\n");
        }
        System.out.println(sb.toString());
    }
}

---

참고

https://tussle.tistory.com/936