알고리즘매일매일

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE

D2문제 중 가장 맨 앞에 있지만 아껴뒀던 문제이다. 문제를 처음 봤을 때 어떻게 풀어야 될지 감이 안 왔고 정답률도 낮았기 때문이다.

먼저 처음에 완전 탐색을 해야 하나? 했지만 N 범위가 너무 커서 포기했다.

어떻게 풀어야 하나 고민하다가 다른 분들이 뒤에서부터 풀면 된다고 쓴 댓글을 보고 힌트를 얻고 풀었다ㅠㅠ

풀이

1. 먼저 N 을 입력받으면 N크기의 배열 생성 후에 매매가를 저장한다.
2. 뒤(N-1)부터 계산을 해준다.
3. 밑의 코드에서 i 변수는 파는 날, j 변수는 사는 날이 된다.
4. 앞의 날의 매매가가 현재 매매가보다 작은 동안 계속 tmp(임시 변수)에다가 현재 매매가를 더해주고 앞의 매매가는 빼준다.(파는 값은 더해주고 사는 값은 빼줌)
5. j가 0보다 작아지거나(첫 날 보다 앞) 현재 매매가보다 큰 값을 발견하면 while문을 종료
6. tmp를 ans(최대 이익)에 더해주고 i값을 j+1 값으로 바꿔준다.
   • (파는 날짜를 바꿔준다)
   • (j값이 되어야 하는데 for문에서 바로 i--가 되므로 +1을 해줌)
7. 모든 날짜에 대해 계산을 해줬으면 ans 출력.

여기서 주의할 점은 ans 는 long 타입을 사용하여야 한다. 매매가는 최대 10,000이고 날짜는 최대 1,000,000이므로 최대치를 계산했을 때 int 형의 범위를 넘어갈 수 있다.

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

public class Solution {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st;
        
		for(int tc=1; tc<=T; tc++) {
			int N = Integer.parseInt(br.readLine());
			int[] price = new int[N];
            
            
            //매매가를 저장
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<N; i++) {
				price[i] = Integer.parseInt(st.nextToken());
			}
			
            
			long ans = 0; //long 타입 사용!
            
            //맨 마지막 날짜부터 계산
            //i 날짜가 파는 날, j 날짜가 사는 날이 된다.
			for(int i=N-1; i>=0; i--) {
				
				int j = i-1; //현재 파는 날짜보다 바로 앞의 날짜들을 검사
				int tmp = 0;
				while(j >= 0 && price[i] > price[j]) {
					tmp += price[i]; //파는 날의 매매가를 더해준다.
					tmp -= price[j]; //사는 날의 매매가를 빼준다.
					j--; //앞의 날짜로 이동
				}
                
				ans += tmp; //이익에 더해준다.
				i = j+1; //파는 날을 옮겨준다.
			}
			
			System.out.println("#"+tc+" "+ans);
		}
	}

}