성능 요약
메모리: 315256 KB, 시간: 1048 ms
분류
그리디 알고리즘
제출 일자
2024년 9월 10일 15:09:59
문제 설명
홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.
- 주식 하나를 산다.
- 원하는 만큼 가지고 있는 주식을 판다.
- 아무것도 안한다.
홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.
예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이 된다.
입력
입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다. 날 별 주가는 10,000이하다.
출력
각 테스트케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다. 답은 부호있는 64bit 정수형으로 표현 가능하다.
풀이 (그리디 알고리즘)
그리디 알고리즘 특성상, 풀고 나면 쉽지만... 풀기 전까지는 조금 고민해야 하는 경우가 많다.
풀이 자체는 간단한 편이다.
- 배열을 거꾸로 순회한다.
- 순회하면서 더 큰 수가 나오면 바꾸고, 아니면
최대 수 - 현재 수를 계산해 결과값에 추가한다.
위 두 가지만 따르면 충분히 해결할 수 있는 문제이다.
주의사항
"각 테스트케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다. 답은 부호있는 64bit 정수형으로 표현 가능하다."
64bit 정수형은 자바 기준 long 타입임을 명심해야 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
//그리디 알고리즘 문제
public static void main(String[] args) throws IOException{
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine()); //테스트 케이스
for(int i=0; i<T; i++) {
int N = Integer.parseInt(br.readLine());//배열 수
int[] num = new int[N];
st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {//입력 받기
num[j] = Integer.parseInt(st.nextToken());
}
int max_num = num[N-1]; //최대 이익 수
long result = 0;
//만약 이익이 생길 수 있다면 이익 구하기 아니면 최대 이익 수 갱신
for(int j = N-2; j>=0; j--) {
if(max_num < num[j]) {
max_num = num[j];
}
else {
result += max_num - num[j];
}
}
sb.append(result+"\n");
}
System.out.println(sb.toString());
}
}