[PS] BOJ11501 주식 ( Greedy ) with JAVA

 

11501번: 주식

 

 

◎ 문제 풀이

• 1. 산다 2) 판다 3) 아무것도 안한다. 3가지 경우가 있고 목표하는 n 날에 최대이익을 구하는 문제이니, 처음에는 DP를 발상하였다. 그러나 DP로 풀기에는 한계가 있었다. 주식을 하나 팔 수도, 두 개 팔 수도 있었다. DP로 이런 복잡한 경우의 수까지 고려할 수 없었다.
• 주식은 가장 쌀 때 사서 비쌀때 파는 것이다. 그러므로 그리디 알고리즘이 적합하다.
• 매일 주가를 기준으로 향후 가장 비싼 주가인 날에 팔면 된다. 주가를 내림차순으로 정렬하고 기준일보다 가장 비싼 날에 주식을 팔면 된다. 비싼 날이 없으면 주식을 사지 않는다.

◎ 코드

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

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());

        while(t-- > 0){
            int n = Integer.parseInt(br.readLine());

            int[] days = new int[n];
            int[][] descDays = new int[n][2];
            boolean[] isSold = new boolean[n];
            long ans = 0;

            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0;i<n;i++){
                days[i] = Integer.parseInt(st.nextToken());

                descDays[i][0] = days[i];
                descDays[i][1] = i;
            }

            Arrays.sort(descDays,(i1,i2)-> i2[0] - i1[0] );

            for(int i=0;i<n;i++){
                if(isSold[i]) continue;

                int cost = days[i];

                for(int j=0;j<n;j++){
                    if( cost >= descDays[j][0]) break;
                    if( descDays[j][0] > cost && descDays[j][1] > i){
                        isSold[descDays[j][1]] = true;
                        ans += descDays[j][0] - cost;
                        break;
                    }
                }
            }

            System.out.println(ans);

        }


    }
}