[SWEA] D2 | 백만장자 (JAVA)

코딩 테스트를 준비하며... 이것저것 문제를 풀어보고 있다. 싸피 테스트가 금방이라서 삼성에서하는 SW ExpertAcademy문제를 풀어보았다.... D1도 엄청나게 쉽게 해결하지 못해서 열심히 공부해야 할 듯 하다. 이건 D2문제이다!!

 

문제를 공유하지 말라는 문구가 있어 혹시 몰라 링크를 첨부하겠다.

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

 

코드

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();
            long[] arr = new long[N];
            long max = 0;
            long cost = 0;
            for(int i =0; i<N; i++){
                arr[i] = sc.nextInt();
            }
            for(int j = N-1; j >= 0; j--){
            	if(arr[j]>max)max = arr[j];
                cost += max - arr[j];
            }
		System.out.println("#"+test_case+" "+cost);
		}
	}
}

 

 

풀이

문제는 다 이해가 간다... 그러나 그 이해한 것을 어떤 알고리즘을 적용해 어떻게 풀어야 하는지가 관건이다. 앞에서부터 풀려고 했으나 감이 가질 않았다. 난 생각보다 엄청나게 복잡하게 생각하는듯! 간단하게 해결 되는 것인데.. 이 문제도 역시 그랬다. 뒤에서부터 최대값을 찾고 최대가 아니면 사고! 그러니까 max값에서 빼면된다. 맨 뒤가 최대 라면 안 산다. 그러나 마지막엔 팔거나 안팔거나... 결과는 똑같으니 저렇게 둬도 된다. 그래서 다른 사람들의 블로그를 많이 보면서 해결!! 

함정은 자료형인데 그냥 안전빵으로 계산 값이 있으면 long으로 하는게 좋겠다.