SWEA 1859 백만 장자 프로젝트 Java

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

SW Expert Academy

SWEA의 D2문제인 백만 장자 프로젝트이다.

 

문제를 간단히 설명하자면

N일 만큼의 매매가가 주어지고

하루에 최대 1개만 살 수 있다.

판매는 개수 제한없이 팔 수 있다.

예를 들어

N = 3

1 2 3 이 주어지면

첫째 날 1원을 주고 1개를 사고

둘째 날 2원을 주고 1개를 사고

셋째 날 3원에 2개를 팔면 6-3 = 3원의 이득이 생긴다.

이처럼 테스트 케이스의 개수, N, 매매가가 주어지면

테스트 케이스당 최대 이익을 출력하면 된다.

 

문제 해결방식은

생각해보면 구매는 한 개밖에 안되기 때문에

팔 때의 순이익은 샀을 때의 금액을 빼주면 그게 순이익이 된다.

매매가가 최고치일 때 파는 것이 순이익이 많이 될 것이고

그 최고치가 뒤에 있을수록 이익을 많이 볼 수 있다.

그렇기 때문에 뒤에서부터 최고 매매가일 때 팔도록

구현해주면 된다.

 

자세한 구현 과정은

매매가가 A배열에 들어있다고 할 때 

최대 매매가에 일단 A[N-1]의 값을 넣어둔다.

그 후 N-2부터 0까지 for문을 돌리면서

최대 매매가보다 A[i]의 매매가가 작다면

최대 매매가 - A[i]의 값을 계속해서 더해주고

최대 매매가보다 A[i]의 매매가가 크다면

최대 매매가를 A[i]로 초기화해주면 된다.

 

주의해야 할 점은

N 제한 백만에 매매가 제한은 일만이기 때문에

최대 이익이 int의 범위를 벗어날 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Q1859 {
 
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(reader.readLine());
        StringBuilder sb = new StringBuilder();
        for(int k=1; k<=tc; k++) {
            int n = Integer.parseInt(reader.readLine());
            int [] a = new int[n];
            String [] input = reader.readLine().split(" ");
            for(int i=0; i<n; i++) {
                a[i] = Integer.parseInt(input[i]);
            }
            int max = a[n-1];
            long ans = 0;
            for(int i=n-2; i>=0; i--) {
                if(max>a[i]) {
                    ans += max-a[i];
                } else {
                    max = a[i];
                }
            }
            sb.append("#"+k+" "+ans+"\n");
        }
        System.out.print(sb.toString());
    }
}

아무리 생각해봐도 dp문제인줄 알았는데

그리디적으로 해결할 수 있는 문제였다.

 

그리디적으로도 생각은 해보았지만

항상 내 사고방식은 앞에서 뒤로에서 그친다.

하지만 이문제는 뒤에서 앞으로 오면서 해결해야 한다.

항상 뒤에서 앞으로 오는 방식도 같이 생각하자.