백준_11501 주식(자바) / 그리디 알고리즘

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

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

public class Back_11501 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(br.readLine());
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		for (int tc = 0; tc < testCase; tc++) {
			int cnt = Integer.parseInt(br.readLine());
			long[] sto = new long[cnt];
			long max = 0;
			long ans=0;
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < cnt; i++) {
				sto[i]=Integer.parseInt(st.nextToken());
			}
			
			for (int i = 1; i <= cnt; i++) {
				if(sto[cnt-i]>max) {
					max = sto[cnt-i];
				}else {
					ans+=(max-sto[cnt-i]);
				}
			}
			sb.append(ans+"\n");
		}
		System.out.println(sb);
	}
}

- 앞에서 부터 찾으면 찾기 어려운 문제였습니다.

 

- 따라서 뒤에서 부터 비교를 하면 좀 쉽게 해결할 수 있는 문제입니다.

 

- 로직은 max 값을 만들고, 뒤에서 부터 max 값보다 더 큰 값이면 max 값을 바꾸고, 가만히 있는 작업을 진행합니다.

 

- max 값 보다 작으면 그 자리와 max 값의 차액을 구해줍니다.