문제 링크
문제
티어: 골드 2
알고리즘: 그리디, 수학
입력
출력
각 레시피에 대해, 원하는 초콜릿 온도와 유량을 달성할 수 있으면 "yes"를 출력하고, 불가능하다면 "no"를 출력하세요.
풀이
각 레시피마다 수도꼭지 설정으로 요구되는 온도와 유량을 달성할 수 있는지를 출력해야 한다.
먼저, 온도를 구하는 식을 보면, 다음과 같이 변환할 수 있다.
x1t1 + x2t2 + ... xktk = ϕ * τ;
이 식을 만족시키는 것은 어렵지 않다.
각 x를 ?/t1으로 하고 ?의 값의 합이 ϕ * τ 되는지만 확인하면 된다.
예를 들어 ϕ * τ값이 5000이고, 수도꼭지가 두 개 있을 때
50 0 100
100 50 100
최소 a만큼은 작동시켜야 하기 때문에
0/50, 5000/100 으로 세팅해 준다. 이때 분자의 합이 5000이 되는지 체크해 준다.
첫 번째 수도꼭지의 분자는 최대 5000이 될 수 있으며, 두 번째 수도꼭지의 분자는 10000이 될 수 있다. 그래서 a<= x <= b 조건을 만족하면서 분자의 합을 5000으로 만들 수 있어서 (x1t1 + x2t2 + ... xktk = ϕ * τ) 이 식을 만족할 수 있다.
그런데 유량이 ϕ값 이 되는지도 체크해야 한다. 그래서 첫 번째 식에 두 번째 식을 대입하여 하나의 조건식으로 변환해 봤다. (x1 = ϕ - (x2 + x3 + ... xk))
그 조건식을 정리하면 다음식이 된다.
(t2 - t1)x2 + (t3 - t1)x3 + ... (tk - t1)xk = ϕ * τ - t1ϕ;
이 조건 또한 앞에 방식과 같이 식이 만족하는지 구할 수 있다. 여기서 tk - t1이 0이상 정수여야 증명 과정이 더 단순해지기 때문에 제외되는 x는 가장 작은 t값을 가진 x로 선택해 준다.
여기서 주의할 점은 제외한 x가 a<= x <= b 조건을 만족하는지 추가로 체크해줘야 한다는 것이다.
우리는 앞에 식으로 x1 + x2 + ... xk의 합을 최대로 만들 수 있고, 최소로 만들 수 있다.
왜냐하면 각 x의 분모는 (tk - 제외된 t)이기 때문에 분모가 큰 x에 우선적으로 분자의 값을 할당해 주면 유량의 합은 최소가 되며, 반대로 분모가 작은 x에 우선적으로 분자의 값을 할당해 주면 유량의 합은 최대가 된다. (여기서 유량의 합은 x를 제외한 값임)
유량의 최대, 최소를 구했다면, 제외된 x의 경계선을 구할 수 있다.
x3 = ϕ - (x1 + x2 + x4 .. xk) -> 자기 자신은 제외된 유량의 합임
여기서 최대를 넣으면 x는 최소값이 되고, 최소를 넣으면 최대값이 된다.
그래서 x의 최댓값이 a보다 작거나 x의 최솟값이 b보다 크면 불가능한 경우이므로 이 경우 no를 출력해 주면된다.
이 풀이의 시간 복잡도는 O(K)다.
소스 코드
import java.io.*;
import java.util.*;
class Faucet implements Comparable<Faucet> {
long t, a, b;
Faucet(long t, long a, long b) {
this.t = t;
this.a = a;
this.b = b;
}
@Override
public int compareTo(Faucet o) {
if(this.t < o.t) {
return -1;
} else if(this.t > o.t) {
return 1;
}
return 0;
}
}
public class Main {
static int N, K;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
ArrayList<Faucet> list = new ArrayList<>();
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
list.add(new Faucet(Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken())));
}
K = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
if(N == 1) {
for(int e = 0; e<K; e++) {
StringTokenizer st = new StringTokenizer(br.readLine());
long T = Long.parseLong(st.nextToken());
long Q = Long.parseLong(st.nextToken());
if(list.get(0).a > Q || list.get(0).b < Q || list.get(0).t != T) {
sb.append("no").append("\n");
} else {
sb.append("yes").append("\n");
}
}
System.out.println(sb.toString().trim());
return;
}
Collections.sort(list);
Faucet minF = list.get(0);
list.remove(0);
for(int i=0; i<list.size(); i++) {
list.get(i).t -= minF.t;
}
Collections.sort(list);
for(int e=0; e<K; e++) {
StringTokenizer st = new StringTokenizer(br.readLine());
long T = Long.parseLong(st.nextToken());
long Q = Long.parseLong(st.nextToken());
long V = T * Q - (minF.t * Q); //최종 값
long curV = 0;
for(int i=0; i<list.size(); i++) {
curV += list.get(i).t * list.get(i).a;
}
if(V < curV) {
sb.append("no").append("\n");
continue;
}
//curV <= V인 상태
long left = V - curV;
double max = 0; //t가 작은 값을 우선적으로 채워주기 때문에 가장 큰 값이 됨
for(int i=0; i<list.size(); i++) {
long leftF = (list.get(i).b - list.get(i).a) *list.get(i).t;
if(leftF <= left) {
max += list.get(i).b;
left -= leftF;
} else {
max += list.get(i).a + (double) left/list.get(i).t;
left = 0;
}
}
if(left != 0) {
sb.append("no").append("\n");
continue;
}
if(minF.b < Q - max) {
//가장 작은 값이 b보다 크다면
sb.append("no").append("\n");
continue;
}
left = V - curV;
double min = 0; //t가 큰 값을 우선적으로 채워주기 때문에 가장 작은 값이 됨.
for(int i=list.size() - 1; i>=0; i--) {
long leftF = (list.get(i).b - list.get(i).a) *list.get(i).t;
if(leftF <= left) {
min += list.get(i).b;
left -= leftF;
} else {
min += list.get(i).a + (double) left/list.get(i).t;
left = 0;
}
}
if(Q - min < minF.a) {
//가장 큰 값이 a보다 작다면
sb.append("no").append("\n");
continue;
}
sb.append("yes").append("\n");
}
System.out.println(sb.toString().trim());
}
}