문제
https://www.acmicpc.net/problem/11501
여담
SWEA에서 풀었던 백만 장자 프로젝트랑 거의 같은 문제인 것 같다. 그치만 기억하는 풀이 방법이 확실하지 않아서 풀이를 참고했다..ㅎ
요즘 들어 느끼는데 안 좋은 습관이 있는 것 같다. 이미 풀었던 문제는 풀이를 약간 기억하고 있는 경우가 많아서 그 기억을 기반으로 문제를 풀려고 한다. 또 "이미 풀었던 문제인데도 못 풀어..??" 라는 생각 때문에 비교적 빨리 풀이를 보고 문제를 푸는 것 같다. 이미 풀었던 문제라도 그 풀이를 도출하는 과정이 중요한 것이니까 제발 기억을 기반으로 풀지 말고 생각을 하고 풀자!
ps. 그리디는 진짜 어려운 것 같다. 많이 풀어보고 이미 풀었던 문제도 다시 풀어보는 것이 정답인 듯..
풀이
주식을 구입한 가격과 주식을 판매하는 가격의 차이가 클수록 주식에서 최대 이익을 얻을 수 있다. 따라서 역방향으로 탐색을 하면서 주식의 가격이 가장 높을 때를 기록한다. 현재 주식의 가격이 최고 가격보다 낮으면 주식을 구매하고, 그렇지 않으면 최고 가격을 갱신(= 아무것도 하지 않는 것)하면 된다.
주식의 가격이 1 1 3 1 2
라면 다음과 같이 행동할 때 최대 이익을 얻을 수 있다.
- 첫째 날과 둘째 날에 주식을 구매하고 셋째 날에 주식을 판매하기 (
(3 - 1) + (3 - 1) = 4
) - 넷째 날에 주식을 구매하고 다섯 째 날에 주식을 판매하기 (
2 - 1 = 1
) - 따라서 최대 이익은 5 (
4 + 1
)이 된다.
즉, 정리하면 다음과 같다.
- 주식의 최대 가격 > 현재 주식의 가격
- 주식 구매하기
total += max - arr[i]
- 주식의 최대 가격 ≤ 현재 주식의 가격
- 주식의 최대 가격 갱신하기(= 아무것도 하지 않기)
max = arr[i]
코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for (int t = 0; t < T; t++) {
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int max = arr[N - 1];
long total = 0L;
for (int i = N - 2; i >= 0; i--) {
if (arr[i] < max) { // 주가가 가장 높을 때보다 낮은 가격인 경우라면
// 주식 사기
total += max - arr[i];
} else { // 주가가 가장 높을 때보다 더 높은 가격인 경우라면
// 최고 주가 갱신하기
max = arr[i];
}
}
sb.append(total).append("\n");
}
System.out.println(sb.toString());
}
}
참고
https://tussle.tistory.com/936
'Algorithm > 그리디' 카테고리의 다른 글
[BOJ] 1700: 멀티탭 스케줄링 (JAVA) (0) | 2024.06.15 |
---|---|
[BOJ] 문제 풀이 모음집 - 그리디 (JAVA) (0) | 2024.06.10 |
[BOJ] 2457: 공주님의 정원 (JAVA) (0) | 2024.04.14 |
[BOJ] 2170: 선 긋기 (JAVA) (0) | 2024.04.12 |
[BOJ] 1744: 수 묶기 (JAVA) (0) | 2024.04.11 |