[SWEA 1859 / JAVA] 백만 장자 프로젝트

[SWEA 1859 / JAVA] 백만 장자 프로젝트

 

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&

SW Expert Academy

 

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.

다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.

다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.

    1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
    2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
    3. 판매는 얼마든지 할 수 있다.

예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.

 

풀이:

문제를 분석해본 결과 다음과 같이 중요 포인트를 정리할 수 있었다.

 

- 첫째날이 최고 매매가이고 다음날로 갈수록 금액이 적어지는, 우하향 직선그래프를 하고 있다면 아무것도 사지 않아야 한다. (10 8 3 2 이런식)

- 그게 아니라면 최고 매매가를 1번째 체크포인트로 두고 그 전날까지 금액이 얼마든 모두 매입한다. 매입한 것을 모두 최고가에 판다.

- 최고 매매가 이후 배열에서 또 2번째 최고 매매가를 구한다. 1번째 최고 매매가 다음날부터 2번째 최고 매매가 전날까지 또 금액이 얼마든 모두 매입하고, 매입한 것을 2번째 최고가에 판다.

- N일이 다 끝날 때까지 위를 반복한다.

 

예를 들어

3 8 9 2 1 14 5 2 9 1

이런 식이라면

14원일 때까지 모두 매입한다음 (3 8 9 2 1원에 매입) 그걸 모두 14원에 팔고, 또 5 2원에 매입한걸 9원에 파는 것이 가장 큰 수익을 낼 수 있다.

 

 

이 문제를 해결하기 위해 다음과 같이 코드를 구상하였다.

 

1. N일 동안의 매매가를 배열로 입력받는다.

2. 전체 배열의 최댓값을 파악한다. 

3. a[최대값의 위치] 전까지 모두 구매한다. 만약 최댓값이 현재위치(배열의 처음)일 경우 그냥 넘어간다.

4. 다시 a[최대값의 위치] 이후 매매가 중 최댓값을 파악한다.

5. 다시 a[2번째 최댓값의 위치]까지 모두 구매한다. 만약 최댓값이 현재위치(남은 배열의 처음)일 경우 그냥 넘어간다.

6. 배열의 끝까지 반복한다.

7. 계산한 수익금을 출력한다.

 

**이때 test case 7/10으로 통과되는 경우**

출력할 총 순이익을 Long 형으로 선언해야 한다.

int로 할 경우 오류가 발생한다. 

 

코드:

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 a = sc.nextInt();
            int arr[] = new int[a]; // 매매값 배열

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



            int max = 0; // 최댓값
            int maxloc = 0; // 최댓값의 위치 a[maxloc]
            Long profit = 0L; // 출력할 전체 순이익 **중요** int로 하면 에러발생 
            int currloc = 0; // 현재 위치 a[currloc]

            while (currloc < a) { // 현재 위치가 배열의 끝일 때까지 반복한다

                for (int i = currloc; i < a; i++) { // 현재 위치부터 끝까지의 최댓값 조사
                    if (arr[i] > max) {
                        max = arr[i]; // 최댓값과 최댓값 위치 저장
                        maxloc = i;
                    }
                }

                if (maxloc != currloc) { // 최댓값이 현재 위치가 아니라면 (현재 위치일 경우 구매하지 않아야 하니 pass)

                    int sum = 0; // 총 매입 금액을 저장할 변수
                    int count = 0; // 총 매입 개수

                    for (int i = currloc; i < maxloc; i++) { // 현재 위치부터 최댓값 전날까지

                        sum = sum + arr[i]; // 총 매입 금액을 더해간다
                        count++; // 총 매입 개수를 더해간다

                    }

                    profit = profit + (arr[maxloc]*count) - sum; 
                    // 현재 순이익 = 이전에 계산한 순이익(초기값 0) + 판매 금액(최고 매매가) * 판매 개수 - 매입 금액

                }
                currloc = maxloc + 1; // 현재 위치를 최댓값 다음날로 업데이트 (그 다음날부터 또 두번째 최댓값 조사해야 하니까)
                max = 0; // 최댓값 초기화


            }

            System.out.printf("#%d ", test_case);
            System.out.println(profit);



        }
    }
}

 

코드 길이도 시간도 단축시킬 수 있는 더 나은 방법이 분명히 있는데.....

내 스스로 해결할 수 있는 코드는 이게 최선이다