Life Engineering
[SW Expert 1859] 백만 장자 프로젝트 (JAVA) 본문
package ssafyjava01;
import java.util.Scanner;
public class SW1859 {
static int T, N;
static long sum, max;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
T=sc.nextInt();
for (int i=1; i<=T; i++) {
N=sc.nextInt();
sum=0;
max=0;
int[] arr=new int[N];
for (int j=0; j<N; j++) {
arr[j]=sc.nextInt();
}
for (int j=N-1; j>=0; j--) {
if (arr[j]>max) {
max=arr[j];
}
else {
sum+=(max-arr[j]);
}
}
System.out.printf("#%d %d\n",i,sum);
}
}
}
꽤나 고민했던 문제..
분명 앞에서부터 탐색하면 지역 최대값이 언제 나오는지 모르므로,
O(N^2) 시간으로 탐색해야 된다..
하지만 뒤에서부터 탐색하게 되면 O(N) 으로 가능하다!!
뒤에서 부터 탐색하는 아이디어를 떠올리는게 어려웠던 것 같다..
뒤에서부터 max값을 구한 뒤 탐색할 때 max값이 새로 갱신될때까지(즉 지금 max보다 큰게 나올때까지) 계속해서 값들을 더해주면 된다.((자기 max 값-자기보다 작은 값)들을 계속 더해줌)
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 다단계 칫솔 판매 (JAVA) (0) | 2022.01.23 |
---|---|
[프로그래머스] 영어 끝말잇기 (Java) (0) | 2022.01.21 |
[BOJ 17135] 캐슬 디펜스 (Java) (0) | 2022.01.19 |
[BOJ 2661] 좋은 수열 (Java) (0) | 2022.01.18 |
[BOJ 17140] 이차원 배열과 연산 (JAVA) (0) | 2022.01.17 |