아니 D1 문제는 그냥 입출력 평균...더하기...이런거더니
갑자기 난이도 올라가는거 실화야..?
쉬운듯 싶은데 어려웠던 문제이다.
괜히 앞에서 부터 계산하겠다고 했다가, 예외사항이 너무 많아서 결국 풀지 못하고 난항을 겪었던 문제인데, 뒤집어서 최댓값을 빼서 계산하는게 포인트라고 한다...(허무하다)
뒤집어서 계산한다는게 무슨 의미인지 알아보도록 하자.
아이디어
예를 들어, 이 문제에는 다음과 같은 테스트 케이스가 주어져 있다.
1,1,3,1,2
이를 뒤집어보면
2,1,3,1,1 이다. 즉,
| 2 | 1 | 3 | 1 | 1 |
|---|---|---|---|---|
| 2 | 2 | 3 | 3 | 3 |
| 0 | 1 | 0 | 2 | 2 |
최댓값을 구한 후, 뒤집은 값과 빼주면 된다. 그리고 더하면 원하는 값을 얻을 수 있다.
나의 경우는 괜히 문제가 주어준 대로 풀겠다고, 배열에 start, end 포인트를 두고 iterate하는 방식을 썼었는데, 항상 알고리즘은 주어진대로 푸는게 아니라 "이 문제를 어떻게 하면 쉽게 해결할 수 있는지를 고민하는게" 해답인 것 같다.
주의 사항
이 문제의 경우, test case가 N(2 ≤ N ≤ 1,000,000)개 존재하는데 각 매매가의 최대가 10,000이하이다. 즉 최대 10^10이기 때문에 int를 사용할 경우 메모리 초과가 발생한다.(알다시피 int는 1,4...해서 10^9까지다.)
그래서 이 문제를 풀때는 정답을 long 형으로 지정해서 풀면 된다.
풀이
import java.util.Scanner;
public class swea_1859 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
for(int i = 1; i <= num; i++) {
int n = sc.nextInt();
int[] list = new int[n];
int[] maxlist = new int[n];
long ans = 0;
int max;
int start = 0;
for(int j = n-1; j>=0; j--) {
list[j] = sc.nextInt(); //거꾸로 저장
}
max = list[0]; //초기값
for(int k = 0; k<n; k++) {
if(max < list[k]) {
max = list[k];
}
maxlist[k] = max;
}
for(int z = 0; z<n; z++) {
ans += (maxlist[z] - list[z]);
}
System.out.println("#" + i + " " + ans);
}
}
}결과
...내일 복습겸 꼭 다시 풀어봐야겠다.
코린이