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

1859 백만 장자 프로젝트 문제 링크

문제분석

• 연속된 N일 동안의 물건의 매매가를 알고있음
• 하루에 최대 1만큼 구입 가능, 판매는 제약없음
• 최대한의 이득 계산

제약 사항

입력 조건

• 첫째 줄 : 테스트 케이스 수 ( T <= 10 )
• 둘째 줄 : N일 (2 ≤ N ≤ 1,000,000)
• 셋째 줄 : 각 날의 매매가 (10,000이하)

출력 조건

• #부호 + 테스트 케이스 번호 + 공백 + 최대 이득 출력

#1

• 재귀를 떠올림..
• 시간 복잡도도 많이 나오고 로직도 뭔가 이상함

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 N = sc.nextInt();
            int[] caseAll = new int[N+1];

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

            long answer = countMax(caseAll, N, 0);
            System.out.println("#" + test_case + " " + answer);

        }
    }

    static long countMax(int[] caseAll, int N, int a) { // a=0;
        //N만큼 반복
        long max = 0L;
        long frontAll = 0L;
        long result;
        long result2 = 0L;
        if(a>=N) return 0;
        for(int i=a; i<=N; i++){
            //다음 값이 떨어지는 수(max)를 찾아 index 구하기
            if(caseAll[i] > caseAll[i+1]) {
                result2 = countMax(caseAll, N, i+1);
                //그 전까지 값을 다 더해(frontAll) & 몇개인지(countM) 구해
                frontAll += caseAll[i];
                max = (long) caseAll[i] * (i-a+1); // max*countM
                break;
            }
            //그 전까지 값을 다 더해(frontAll) & 몇개인지(countM) 구해
            frontAll += caseAll[i];
            max = (long) caseAll[i] * (i-a+1); // max*countM
        }
        //max*countM - frontAll
        result = max - frontAll;
        return result+result2;
    }
}

#2

• 뒤에서부터 돌면서
  • 해당 값이 최댓값이면 최댓값 갱신
  • 해당 값이 최댓값이 아니면 최댓값에서 해당 값을 빼서 결과에 더함

import java.util.Scanner;

class Solution {
    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 N = sc.nextInt();
            int[] caseAll = new int[N];

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

            long answer = countMax(caseAll, N);
            System.out.println("#" + test_case + " " + answer);
        }
    }

    static long countMax(int[] caseAll, int N) {
        long profit = 0;
        int maxPrice = 0;

        for (int i = N - 1; i >= 0; i--) {
            if (caseAll[i] > maxPrice) {
                maxPrice = caseAll[i];
            } else {
                profit += maxPrice - caseAll[i];
            }
        }
        return profit;
    }
}

• 냅다 풀려고 하지말고 좀 더 차분하게 생각해볼 것....