문제 링크
문제
티어: 골드 2
알고리즘: 그리디, 수학
입력
출력
각 테스트 케이스에 대해 한 줄씩 결과를 출력하세요. 각 테스트 케이스의 결과로, 모든 소들의 배고픔 수치를 동일하게 만들기 위해 필요한 최소 옥수수 자루의 수를 출력하거나, 불가능하다면
−1을 출력하세요.
풀이
농부 존이 소들의 배고픔 수치를 동일하게 만들기 위해 필요한 최소 옥수수 자루의 수를 구해야 한다. 만약 불가능한 경우는 -1를 출력한다.
최소 옥수수 자루를 사용하기 위해서는 가장 작은 값을 가능한 선에서 고정시키는게 중요하다. 작은 값이 동일한 수의 기준이기 때문이다.
그래서 현재 상태에서 가장 작은 값을 min에 저장해 준다.
그리고 첫 번째 소를 보자.
첫 번째 소가 min이라면 옥수수 자루를 먹일 필요가 없다.
min보다 크다면 min으로 맞춰줘야 하기 때문에 cnt = 배고픔 수치 - min 만큼 옥수수 자루를 먹여야 한다.
그런데 먹이를 줄 때는 인접한 소 (i, i+1)와 같이 줘야되기 때문에 다음 소도 cnt 만큼 옥수수 자루를 먹야야 한다.
만약 다음 소에게 cnt만큼 먹였는데 -가 된다면 이 경우는 불가능한 경우가 된다.
왜냐하면 결국 현재 소를 min으로 맞춰줘야 하는데 앞의 소와 맞춰줄 수 없으면 뒤의 소와 맞춰주는 방법밖에 남지 않고, 뒤에 소는 이미 min 값을 가지기 있어 min을 더 낮추는 방법이 된다.
그래서 우리는 앞의 소만 살펴보면 되는 것이다.
그러면 현재 소가 min보다 작은 값을 가지면 어떻게 될까?
이 경우는 아직 불가능하다고 판단하기 이르다. min을 일단 현재 소의 값으로 업데이트 시켜주고, 지금까지 지나왔던 소의 수를 봐야한다.
만약 그 수가 짝수라면 두 소씩 짝 지어서 새로운 min으로 업데이트가 가능하다. (지나온 모든 소의 배고픔 수치는 전 min값을 가지고 있음)
-> answer += (지나온 소의 수) * (beforeMin - curMin);
만약 그 수가 홀수인 경우는 두 소씩 짝을 지을 수 없기 때문에 이 경우는 불가능한 경우가 된다.
이렇게 N-2까지 반복하고, 마지막 소는 다음 소가 없기 때문에 다르게 처리해야 한다.
마지막 소의 배고픔 수치가 현재 min과 같다면 지금까지 먹이로 준 옥수수 자루의 수인 answer을 출력한다.
만약 min보다 크다면 이 경우는 불가능한 경우다. 왜냐하면 min을 맞춰주기 위해서 먹이를 줘야 하는데 뒤에 소와 인접해서 줘야하기 때문에 min값을 계속 낮추기 때문이다.
만약 min보다 작다면 앞에서 말했던 것처럼 짝수인지 홀수인지를 판단하고
홀수라면 -1를
짝수라면 answer += (N -1) * (beforeMin - curMin); 해주고 answer을 출력해 준다.
이 풀이의 시간 복잡도는 O(N)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int T;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int r = 0; r < T; r++) {
int N = Integer.parseInt(br.readLine());
int[] line = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
int min = Integer.MAX_VALUE;
for(int i=0; i<N; i++) {
line[i] = Integer.parseInt(st.nextToken());
min = Math.min(line[i], min);
}
if(N == 1) {
sb.append(0).append("\n");
continue;
}
long answer = 0;
for(int i=0; i<N - 1; i++) {
if(line[i] == min) {
continue;
}
if(line[i] < min) {
if(i % 2 == 1) {
answer = -1;
break;
}
min = line[i];
answer += (long) (line[i - 1] - min) * (long) i;
continue;
}
//현재 값이 min 값보다 큰 경우임
int cnt = line[i] - min; //min 값으로 맞춰주기 위해서 필요한 횟수
if(line[i + 1] - cnt < 0) {
//min을 못만드는 경우임
answer = -1;
break;
}
//만들 수 있는 경우
line[i] -= cnt;
line[i + 1] -= cnt;
answer += (long) (cnt) * 2;
}
if(answer != -1) {
if(line[N - 1] > min) {
answer = -1;
} else if(line[N - 1] < min) {
if((N-1) % 2 == 1) {
answer = -1;
} else {
answer += (long) (min - line[N - 1]) * (long) (N -1);
}
}
}
sb.append(answer).append("\n");
}
System.out.println(sb.toString().trim());
}
}