SWEA [D2] 백만 장자 프로젝트 - 1859 JAVA

링크텍스트

설명

풀이 흐름 설명

분명 풀이 방식은 맞는 것 같은데 오답이 나왔다.
원인은 이익의 합을 저장하는 sum 변수를 int로 선언한 것이었다.

이 문제에서는 N이 크고 가격 차이도 커질 수 있기 때문에 누적 이익이 int 범위인 약 21억을 초과할 수 있다. 로직은 맞더라도 계산 과정에서 오버플로우가 발생하면 잘못된 값이 저장된다.
그래서 sum을 int가 아닌 long으로 변경했고 그 결과 정상적으로 통과할 수 있었다.
시간복잡도: O(N), 공간복잡도: O(N)

회독

• [ x ] 1회
• 2회
• 3회

코드

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
    static StringBuilder sb = new StringBuilder();
	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();
            int [] arr = new int [n];

            for(int i=0;i<n;i++){
                arr[i] = sc.nextInt();
            }
            
            long sum = 0;
            int now = arr[n-1];
            for(int i=n-1;i>=0;i--){                
                if(now>arr[i]){
                    sum+=(now-arr[i]);
                }else now = arr[i];
            }
			
            sb.append("#").append(test_case).append(" ").append(sum).append("\n");
		}
        
        System.out.print(sb);
	}
}