1859. 백만 장자 프로젝트

미래를 예측하는 이가 하루마다 바뀌는 물건의 시세를 알고 있다.

테스트케이스 수, 시세 변동 날, 물건의 시세를 입력값으로 받는다.

미래를 예측하는 이의 가장 큰 이득을 예상하라는 문제였다.

 

예시로, 입력값이 

3 //테스트 케이스 수
5 //케이스1의 시세 변동 총 날짜
1 2 3 4 5 //케이스1의 5일동안의 시세 변동
4 //케이스2의 시세 변동 총 날짜
2 5 1 3 //케이스2의 4일동안의 시세 변동
3 //케이스3의 시세 변동 총 날짜
5 4 3 //케이스3의 3일동안의 시세 변동

일 때, 

 

출력값은 다음과 같다.

#1 10 // 1일부터 4일까지 물건을 구매해서 가장 높은 5일에 판매하면 예상 최대 이익은 4, 3, 2, 1을 더해 총 10
#2 5 // 3일의 5원때 2원으로 첫 째날에 구매해 3원의 이득과 3일차 때 1원으로 구매해 마지막날 3원으로 판매해 총 4원의 이득
#3 0 // 갈수록 하락하여 이득을 취할 수 없음

 

그렇게 가장 먼저 접근했던 방식은 시세가 점차 증가 추세일 때, 변수 down에 해당 시세 값을 더해주고 최고가에서 각 편차들을 더해주기 위해 temp 변수에 매 회마다 1씩 더해준다. 그 후 만약 최고가보다 최소값이 나왔을 때, 해당 최고가에서 temp를 곱한 후 down에 더해놨던 시세들을 빼주면 해당 최고가 그 전의 시세들의 이득들의 합을 더할 수 있다.

 

예시로, 입력값 테스트 케이스 1의 경우 5일차 최고가 전 까지 시세 1, 2, 3, 4들을 계산할 때까지 down의 변수는 10(1+2+3+4), temp 변수는 4(1+1+1+1)일 것이다. 5일차 때 최고가이므로 내가 생각했던 방법을 쓰면 5(최고가)*4(temp) - 10(down)으로 출력값은 10이 된다. 

 

해당 방식의 코드는 다음과 같다.

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

class D2_1859
{
    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 day = sc.nextInt();
            sc.nextLine();

            int[] dayCoin = new int[day+1]; //for문에서 다음 원소와 비교할 때 마지막 원소 비교를 위해 마지막에 0을 넣어줌

            for(int i = 0; i < day; i++){
                dayCoin[i] = sc.nextInt();
            }

            sc.nextLine(); // 줄바꿈을 없애줌

            int result = 0; // 결과값
            int down = 0; // 증가세일 때 전의 숫자를 더해줄 변수
            int temp = 0; // 증가세일 때 전의 숫자를 더해 가장 최고가일 때 증가세의 합을 temp * 최고가에서 빼줄 때 사용할 변수

            for(int i = 0; i < day; i++){
                if(dayCoin[i] <= dayCoin[i+1]){
                    down += dayCoin[i];
                    temp ++;
                }
                if(dayCoin[i] > dayCoin[i+1]){
                    result += dayCoin[i]*temp - down;
                    down = 0;
                    temp = 0;
                }
            }
            System.out.printf("#%d %d", test_case, result);
            System.out.println();
        }
    }
}

일단 코드 작성은 내가 예상했던 방식으로 잘 짜여졌고 출력값도 잘 나왔다. 여기서 문제점을 몇개 꼽자면 

 

1. 해당 문제는 상당히 많은 양의 데이터를 처리할 수 있고 많은 양의 테스트케이스가 존재할 수 있어서 배열을 다루는 로직 특성상 런타임 에러가 발생할 가능성이 있었다.

 

2. 배열을 계산하면서 처음 최고가를 찍고 다시 가격이 내려갈 때 이익을 계산하는 형태였는데  만약에 그 후에 계산했을 시점보다 더 높은 최고가가 나왔을 때를 감안해야하는지 궁금했다. 예시로 입력 케이스로 6일 동안 시세 변동이 1, 2, 3, 2, 4, 6으로 들어왔을 때, 내가 작성한 코드의 예상 출력값은 9가 될 것이다. 하지만 만약에 가장 최고가인 6으로만 계산한다면 출력값은 5+4+3+4+2로 18이 되어야 한다. 

 

그렇게 2번의 케이스의 경우 코드를 돌려보고 수정하면 되는 것이므로, 코드를 실행해보았으나 역시 런타임 에러가 발생했다. 2의 문제여도 런타임에러는 수정하지 않는 한 또 일어날 것이므로, 1번 문제의 가능성을 중점으로 코드를 수정해보았다. 

 

해결책을 생각하고 혹시나 해서, 각 변수들의 데이터타입을 long으로 바꾸어주었더니 런타임에러가 발생하지 않고 오답이라는 메시지가 떴다. 결국 2번문제가 이유일거라고 생각하고 배열을 사용하지 않는 것과, 시세처리 방식을 배열의 뒤에서부터 계산하기로 해보았다.

 

그렇게 수정된 최종 코드

import java.util.Scanner;

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

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

            for (int i = 0; i < day; i++) {
                prices[i] = sc.nextInt();
            }

            int maxPrice = 0;
            long result = 0; // 이익 계산 변수 (long 타입으로 오버플로우 방지)

            // 뒤에서부터 최대값을 찾아서 이익을 계산
            for (int i = day - 1; i >= 0; i--) {
                if (prices[i] > maxPrice) {
                    maxPrice = prices[i];  // 현재까지의 최대 가격 갱신
                } else {
                    profit += maxPrice - prices[i];  // 현재 가격이 최대 가격보다 낮으면 이익 계산
                }
            }

            System.out.printf("#%d %d\n", test_case, result);  // 결과 출력
        }
        sc.close();
    }
}

짜란! 접근 방식과 사재기 이득 계산 방식에 착오가 있었던 것 같다.