[SWEA] D2 1859 백만 장자 프로젝트 자바(Java)

문제 링크

SW Expert Academy

 

풀이

처음 풀이는 배열 첫 번째 부터 큰 값을 찾고 다음 값이 작아지면 가장 컸던 max 값을 기준으로 그 전 값들을 판매한 이익을 더해서 풀이했다.

첫 3개 정도의 테스트 케이스는 맞았지만 나머지는 정답과 다르게 나왔다.

타입을 Long으로도 바꾸고 했지만 배열 끝부터 검사하여 작은 값들을 카운트해서 계산하니 원하는 정답이 나올 수 있었다. 

쉽게 풀 것 같았지만 생각보다 어려웠던 문제였다..

 

풀이 코드

import java.io.*;
import java.util.*;

public class Test {
	public static int n;
	public static long result = 0;
	public static int arr[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int test_case = 1; test_case <= T; test_case++) {
			n = sc.nextInt();
			arr = new int[n];
			result = 0;

			for (int i = 0; i < n; i++) {
				arr[i] = sc.nextInt();
			}

			sumProfit(test_case, arr);
		}
	}

	public static void sumProfit(int testCase, int arr[]) {
		long max = Integer.MIN_VALUE;
		int cnt = 0;
		long cost = 0;

		for (int i = arr.length - 1; i >= 0; i--) {
			if (arr[i] > max) {
				result += (max * cnt - cost);
				max = arr[i];
				cost = 0;
				cnt = 0;
			} else {
				cost += arr[i];
				cnt++;
			}
		}
		result += (max * cnt - cost);

		System.out.println("#" + testCase + " " + result);
	}
}