[swexpert] 1859. 백만장자 프로젝트 (java)

함정: 데이터 범위 초과 

푸는 방법: 뒤에서 부터 돌면서 풀기 

 

1) 풀이 

3 5 9의 경우 뒤집어서 9 5 3 으로 본다 

 

1. max_value를 갱신해나간다 

2. max_value - 현재 값을 결과값으로 더해 나간다. 뒤에서부터 도는 이유는 나중에 나오는 가장 큰 값을 찾기 위해서이다.

 

current_value	9	5	3
max_value	9	9	9
diff=max_value-current_value	0	4	6

답은 모든 차이값 diff를 더한 값이다.

 

2) 함정

 

n은 총 1000000로 10^6이고 각 금액의 최대값은 10000이다. 즉 모든 금액이 10000이고 n=10^6이라면 

모든 값을 다 더한 결과값이 최대 10^4*10^6 = 10^10 로 메모리가 초과하게 된다.

(int의 크기는 최대 2^16-1, 대략 2^10 = 10^3으로 계산) 

 

따라서 long형을 써준다. 여기서는 diff만 long형이 되면 된다.

 

import java.util.Scanner;

public class Solution {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		for (int i = 0; i < t; i++) {
			int n=sc.nextInt();
			long diff=0;
			int max_value=0;
			int[] arr=new int[n];
			for (int j = 0; j < n; j++) {
				arr[j]=sc.nextInt();
			}
			for (int j = n-1; j >=0; j--) {				
				if(arr[j]>max_value)max_value=arr[j];
				diff+=max_value-arr[j];
			}
			System.out.printf("#%d %d\n",i+1,diff);
		}
		sc.close();
	}
	
	
}