[백준]11501번, 주식

백준, Q11501 주식

문제 :

홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.

1. 주식 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.

홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.

예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이 된다.

 

입력 :

입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다. 날 별 주가는 10,000이하다.

 

출력 :

각 테스트케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다. 답은 부호있는 64bit 정수형으로 표현 가능하다.

 

<소스 코드>

import java.util.*;
 
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
 
        for (int test_case = 0; test_case < T; test_case++) {
            int N = sc.nextInt(); int[] stock = new int[N+1];
            long gain = 0;
            int max=0;
 
            for(int i = 0; i < N; i++)
                stock[i] = sc.nextInt();
 
            for(int i = N-1; i > -1; i--){//뒤에서 부터 비교
                if(stock[i] > max) // 현재 가격이 지금까지 가장 비쌀때 보다 크다면  
                    max = stock[i]; // max = stock[i]
                else
                    gain += (max - stock[i]);//아니면 팔았을 때 이득을 더 해준다.(가장 비싼가격 - 현재 가격)
            }
            System.out.println(gain);
         }
    }
}

 

<실행 결과>

 

 

<해법>

생각보다 풀기 어려운 문제다. 필자는 주가가 최대치를 찍고 주가가 하락할 떄 팔게 알고리즘을 짰다. 그러나 이는 최대 이익을 볼 수 없는 방법이다. 최대 이익을 보려면 아래와 같이 접근해야 한다.

 

- 잘못된 접근: 주가가 떨어지는 시점에 기존 구입했던 주식 판매 (Greedy)

- 올바른 접근: 주가가 떨어지는 시점이 아니라, 현재 주가를 현재일 이후에 가장 비싸게 팔 수 있는 날에 판매

*접근법 정리 출처 : https://www.acmicpc.net/board/view/16527

 

즉, 가장 비싸게 팔 수 있는 날까지 등락 관계없이 주식을 사야한다. 그리고 주식을 판 이후에 날(N)이 남았을 때도, 판날로 부터 가장 비싸게 팔 수 있는 날을 한번 더 고려해 이익을 계산해야 한다.

 

알고리즘은 뒤에서 부터 비교해서 짜면 더 쉽게 짤 수 있다.

 

앞에서 부터 계산하면 주식을 판 다음 날 부터 다시 최댓값을 구하는 알고리즘을 구현해야 한다.

하지만 뒤에서 부터 비교하면 가장 비쌀 때 이후의 가격들을 먼저 찾아 계산하므로 더 쉽게 코드를 짤 수 있다.

 

for N 부터 0까지

if 현재 주가(stock[i]) > 현재까지 비싼 가격(max) 

max = 현재 주가(stock[i])

else

이익(gain) += 가장 비쌀 때 가격 - 현재 가격

 

 

 

문제 사이트 및 참고 사이트 : https://www.acmicpc.net/problem/11501

※
본 게시물은 개인적인 용도로 작성된 게시물입니다. 이후 포트폴리오로 사용될 정리 자료이니 불펌과 무단도용은 하지 말아주시고 개인 공부 목적으로만 이용해주시기 바랍니다.

※