백준 - 주식

코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] arr = new int[N];
            for (int j = 0; j < N; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }

            long answer = 0;
            int cur = arr[N-1];

            for (int j = N-1; j >= 0 ; j--) {
                if (arr[j] <= cur) {
                    answer += cur - arr[j];
                } else {
                    cur = arr[j];
                }
            }
            System.out.println(answer);
        }
    }
}

풀이

🤓해당 문제는 그리디 알고리즘으로 생각하시면 풀 수 있는 문제입니다.

1. 가장 큰 이익을 찾기 위해서는 배열의 마지막 부분부터 시작을 해야 하는데 마지막 부분을 가장 큰 값으로 생각하고 for문을 수행하면서 자기보다 큰 값이 나오기전까지는 모두 주식을 산다고 생각하시면 됩니다.
2. 자기보다 작으면 answer에 값을 더해주고 만약 자기보다 큰값이 나오게 된다면 해당 배열을 기준으로 다시 위 과정을 거쳐주시면 됩니다.

출처 : 백준 - 11501번