[백준 11501번] 주식

https://www.acmicpc.net/problem/11501

package greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Greedy11501 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            long[] arr = new long[N];
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }
            long compare = arr[N - 1];
            long p_sum = 0;
            long cnt = 0;
            long sum = 0;
            boolean flag = false;
            for (int j = N - 2; j >= 0; j--) {
                if (compare < arr[j]) {
                    sum += compare * cnt - p_sum;
                    compare = arr[j];
                    p_sum = 0;
                    cnt = 0;
                    flag = true;
                } else {
                    flag = false;
                    p_sum += arr[j];
                    cnt++;
                }
            }

            if (!flag) {
                sum += compare * cnt - p_sum;
            }
            System.out.println(sum);
        }

    }
}

 

저번에 SWEA에서 풀었던 문제인데 또 나왔다!!!

이번 문제 핵심은 그냥 역순으로 돌려서 처음 기준 값보다 큰 값이 나오면 큰 값까지 이동한 위치 수만 큼 계산해서 구하는 알고리즘이다. 하지만 출력 값 64bit를 long으로 하지 못해 틀렸다... long 주의하자!