[D2 SWexpert] 백만장자 되기

문제 분석

각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,

둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.

각 날의 매매가는 10,000이하이다.

-> N개와 매매가가 모두 최대라고 치면, 매매가 만원을 모두 백만 개 사게 되면 int타입으로는 표현할 수 없다. (int는 최대 21억까지만 가능한 것 같음.) 따라서 이익은 long타입으로 선언해줘야 한다.

알고리즘

값들 중에서 가장 큰 값을 가진 날에 팔아야 되기 때문에,
오늘 매매가를 계속 더해주다가 매매가가 큰 날에 팔면 된다. 그럼 이익은 (큰 매매가 - 오늘 매매가) 를 계속 더한 값이 될 것이다.
그리고 앞에서 부터 찾는거보다는 뒤에서부터 계산해주면 된다. 만약, N이 백만이라면 앞에서 백만까지 찾으면 오버플로우가 발생할 수도 있기 때문이다.

코드

/////////////////////////////////////////////////////////////////////////////////////////////
// 기본 제공코드는 임의 수정해도 관계 없습니다. 단, 입출력 포맷 주의
// 아래 표준 입출력 예제 필요시 참고하세요.
// 표준 입력 예제
// int a;
// double b;
// char g;
// String var;
// long AB;
// a = sc.nextInt();                           // int 변수 1개 입력받는 예제
// b = sc.nextDouble();                        // double 변수 1개 입력받는 예제
// g = sc.nextByte();                          // char 변수 1개 입력받는 예제
// var = sc.next();                            // 문자열 1개 입력받는 예제
// AB = sc.nextLong();                         // long 변수 1개 입력받는 예제
/////////////////////////////////////////////////////////////////////////////////////////////
// 표준 출력 예제
// int a = 0;                            
// double b = 1.0;               
// char g = 'b';
// String var = "ABCDEFG";
// long AB = 12345678901234567L;
//System.out.println(a);                       // int 변수 1개 출력하는 예제
//System.out.println(b); 		       						 // double 변수 1개 출력하는 예제
//System.out.println(g);		       						 // char 변수 1개 출력하는 예제
//System.out.println(var);		       				   // 문자열 1개 출력하는 예제
//System.out.println(AB);		       				     // long 변수 1개 출력하는 예제
/////////////////////////////////////////////////////////////////////////////////////////////
import java.util.Scanner;
import java.io.FileInputStream;

/*
   사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
   이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
 */
class Solution
{
	public static void main(String args[]) throws Exception
	{
		/*
		   아래의 메소드 호출은 앞으로 표준 입력(키보드) 대신 input.txt 파일로부터 읽어오겠다는 의미의 코드입니다.
		   여러분이 작성한 코드를 테스트 할 때, 편의를 위해서 input.txt에 입력을 저장한 후,
		   이 코드를 프로그램의 처음 부분에 추가하면 이후 입력을 수행할 때 표준 입력 대신 파일로부터 입력을 받아올 수 있습니다.
		   따라서 테스트를 수행할 때에는 아래 주석을 지우고 이 메소드를 사용하셔도 좋습니다.
		   단, 채점을 위해 코드를 제출하실 때에는 반드시 이 메소드를 지우거나 주석 처리 하셔야 합니다.
		 */
		//System.setIn(new FileInputStream("res/input.txt"));

		/*
		   표준입력 System.in 으로부터 스캐너를 만들어 데이터를 읽어옵니다.
		 */
		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 profit = 0;  // n = 백만이고, 금액은 최대가 만원이므로 곱하면 천억, 즉 int로 표현 불가.
            int max = 0;
            //뒤에서부터 최대값에서 작은 값을 계속 빼주는 구조로 간다.
            for(int i = N-1; i>=0; i--){
                //만약 내 뒤에 더 큰 수가 나오면, 구매한다. 이익: 최대 - 오늘 금액
                int today = arr[i];
                if (max > today){ //내 뒤에 더 큰수가 있다면, 구매하는 것.
                    profit+= max - today; 
          		}
               else{ //오늘이 더 클 때
                   max = today; 
               }
			}
            System.out.println("#"+test_case+" "+profit);
        }
    }
}

}
``

내가 생각한 방법

나는 어떻게 풀려고 했냐면 max값을 찾는걸 반복하려고 했었다.......
근데 그냥 뒤에서부터 하면 됐었음...
유튜브를 봤따. 그냥 보는게 나음

후기

이런 기업 코테 첨 풀어보는데(?) 뭐 기업 코테라고 하기도 뭐하지만 D2이라.... 근데 메모리 제한 시간도 있고 런타임 제한 시간도 있는게 너무너무 신기하기도 하고 걍 노답이다 물론 내가....나 어쩌지??ㅎㅎ 나 지짜 코딩 못한다고 느낌...진심 4학년이 아니라 1학년 같음 ㅠㅠ