[SWEA] 1859 백만 장자 프로젝트(D2)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

 

날짜 최대 개수는 1000000이고, 매매가는 최대 10000이다.

그러면 최대 1000000*10000 정도의 결과가 나올 수 있음 -> int 최댓 값이 20억 정도이니 오버함

=> result 는 long타입으로 결정

 

 

처음에는 local max를 구하는 식으로 문제를 풀려고 했는데, 더 간단한 그리디 방법이 있었음

 

 

1. local maximum을 계속 구하는 풀이

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
	public static void main(String args[]) throws Exception
	{
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++){
            int dayCnt = sc.nextInt();
            int[] prices = new int[dayCnt];
            for (int day =0; day<dayCnt; day++)
                prices[day] = sc.nextInt();

            long result = 0;

            int start = 0;
            while (start < prices.length-1) {
                int localMaxIdx = start;
                int localMax = 0;

                //localMax 찾기
                for (int i = start; i<dayCnt; i++) {
                    if (prices[i] > localMax) {
                        localMaxIdx = i;
                        localMax = prices[i];
                    }
                }

                for (int i=start; i<localMaxIdx; i++)
                    result += (localMax - prices[i]);

                start = localMaxIdx + 1;
            }

            System.out.println("#" + test_case + " " + result);
    	}
    }
}

1. 인덱스 0~(size-1) 까지 최댓값을 구한다
2. 최댓값 앞쪽의 날짜에 대한 (max - price[i]) 값을 모두 result에 더한다 
3. max+1을 시작점으로 인덱스 시작점 ~ (size-1) 까지 최댓값을 구한다
4. 최댓값 앞쪽의 날짜에 대한 (max - price[i]) 값을 모두 result에 더한다
5. ... 반복 -> 인덱스가 size-1이 될 때까지

 

이 방법은 인덱스 계산이 조금 힘들다는 단점이 있다. 구글링을 해보니 더 쉬운 풀이들이 있어 이걸로도 풀어봤다

 

 

2. 뒤에서부터 max값을 갱신하는 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution
{
  public static void main(String args[]) throws Exception
  {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());

    for(int test_case = 1; test_case <= T; test_case++)
    {
      int dayCnt = Integer.parseInt(br.readLine());
      int[] prices = new int[dayCnt];
      StringTokenizer st= new StringTokenizer(br.readLine());

      for (int day =0; day<dayCnt; day++)
        prices[day] = Integer.parseInt(st.nextToken());

      long result = 0;
      int max = prices[dayCnt-1];

      for (int day = dayCnt-2; day >= 0; day--) {
        if (prices[day] >= max) {
          max = prices[day];
        } else {
          result += (max - prices[day]);
        }
      }

      System.out.println("#" + test_case + " " + result);
    }
  }
}

1. 뒤 인덱스부터 최댓값과 비교, 최댓값이면 최댓값을 갱신한다
2. 만약 최댓값보다 값이 작으면 (max - prices[day]) 를 result에 더해준다
3. wihle 인덱스 > 0

(그림으로 그려보면 편하게 이해 가능함)

 

 

 

소감

백준에서 하던 실수 반복중.. 문제를 안풀다보니 감을 잃었다..ㅠㅠㅠ

꼭꼭 최댓값을 적어서 자료형을 먼저 정한 후 문제풀자!