[백준] BOJ 11501 주식(자바/시간 초과)

 

문제  유형

전부 계산해 보는 그리디 알고리즘이다.

 

 

 

 

어려웠던 점

1. 먼저 처음 풀이할 때는 배열을 int i = 0부터 시작하여 최대 수익을 계산했다. 이중 for문을 사용하여 문제를 풀었다. 그랬더니 시간초과가 발생했다.

 

 

 

 

그래서 뒤에서 부터 for문을 돌면서 수익을 낼 수 있으면 결괏값에 더하고, 아닌 경우 max를 갱신했다.

 

 

 

 

틀렸는데 반례를 확인해봐도 도저히 이유를 몰랐다.

이유는 문제에서 찾을 수 있었다.

 

 

 

무심코 넘어갔던 출력 조건인 부호 있는 64bit 정수형으로 표현 가능하다는 조건이 존재한다.

 

여기서 long 타입은 64bit 정수형, int 타입이 32bit 정수형이라는 점이다.

 

따라서, 결과값을 출력할 때 long 타입으로 출력해야 했다.

 

 

 

 

 

 

 

쉬웠던 문제인데 뭔가 실수도 많았던 것 같다. 조건을 잘 파악해서 문제를 풀이해야겠다.

 

 

 

 

---

구현

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		
		for (int tc = 1; tc <= T; tc++) {
			int N = Integer.parseInt(br.readLine());	
			
			int[] maps = new int[N];
			long result = 0;
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				maps[i] = Integer.parseInt(st.nextToken());
			}
			result = solve(maps, result, N);
			
			sb.append(String.format("%d\n", result));
		}
		System.out.println(sb.toString());
	}
	
	
	static long solve(int[] maps, long result, int N) {
		long max = 0;
		for (int i = N-1; i >= 0; i--) {
			if(max > maps[i]) {//수익을 낼 수 있는 경우
				result += max - maps[i];
			}else {
				max = maps[i];
			}
		}
		
		return result;
	}
	
}