문제 링크
문제
티어: 골드 2
알고리즘: 그리디, 정렬, 수학, 확률론
입력
첫 번째 줄에는 1 이상 1,000,000 이하의 정수 n이 주어집니다.
그 다음 n개의 줄에는 wi와 qi가 주어지며, 여기서 1 ≤ wi ≤ 10,000이고 0 < qi < 10,000입니다.
pi는 qi / 10000으로 정의됩니다.
출력
당신이 복권을 선택할 순서를 나타내는 n개의 정수(1부터 n까지)를 한 줄에 출력하세요. 당신이 얻을 수 있는 기대 Vitcoins의 수를 최대로 만드는 순서를 출력해야 하며, 만약 여러 가지 가능한 순서가 있다면 사전순으로 가장 먼저 오는 순서를 출력하세요.
힌트
풀이
기대 Vitcoins의 수를 최대로 만드는 순서를 출력해야 한다.
기대 Vitcoins의 공식은 힌트에도 나와있다.
이를 이용해서 풀이한 과정은 다음과 같다.
A와 B가 있을 때 어떤 순서로 복권을 선택하는게 가치를 최대로 할 수 있을까?
먼저, A -> B순으로 선택했을 때 공식을 구하고
B -> A순으로 선택했을 때 공식을 구한다.
그리고 첫 번째 식을 SA 두 번째 식을 SB라고 할 때
SA < SB보다 크다면 A보다 B를 먼저 선택하는 것이 최선이 된다.
SA < SB 식을 정리하면 다음과 같다.
WA / (1 - PA) < WB / (1 - PB)
그래서 핵심은 WB / (1 - PB) 이 식이며, 이 식의 값을 기준으로 내림 차순 정렬한 것이 답이 된다. (같다면 index가 낮은 순으로 정렬)
여기서 이런 의문이 들 수 있다. 단순히 두 복권일 때 식을 비교하는 것은 다수의 복권이 있을 때 비교하는 것과 다를 수 있다.
그런데 이것은 틀렸다. 만약 세개의 복권이 있다고 했을 때 세 번째부터는 (WA + WB) PA PB이기 때문에 결과적으로 A -> B순으로 하든 B -> A순으로 하든 똑같기 때문이다.
WB / (1 - PB) 이 식을 잘보면 WB는 비트코인을 최대로 얻을 수 있는 수이며, (1 - PB)는 실패할 확률이다. 그래서 가치를 판단하기 위해서는 WB 1/(1-PB)라는 식이 필요할 것 같다는 직감이 든다. (1/(1-PB)는 실패할 확률이 클수록 값이 작아지고, 작을수록 값이 커진다. 그렇기 때문에 WB 1/(1-PB) 이 식의 값이 크다면 가치가 크다고 판단할 수 있다.)
그런데 주의할 점은 W / (1 - P) 이 식을 그대로 사용하면 WA가 되는데 이는 부동소수점 연산의 정밀도가 손실되기 때문이다. (아주 작은 값이나 큰 값을 연산할 때 정밀도가 손실됨)
그래서 이를 정수 연산으로 정확한 정밀도를 나타낼 수 있게 다음과 같이 식을 변형해서 적용해 준다.
10000 * W / (10000 - Q) 이 식을 기준으로 내림차순 정렬해서 출력하면 AC가 된다.
이 풀이의 시간 복잡도는 O(N * logN)이다.
소스 코드
import java.io.*;
import java.util.*;
class Ticket implements Comparable<Ticket> {
double v; //가치
int ind; //인덱스
Ticket(int ind, double v) {
this.ind = ind;
this.v = v;
}
@Override
public int compareTo(Ticket o) {
if(this.v < o.v) {
return 1;
} else if(this.v > o.v) {
return -1;
} else {
if(this.ind < o.ind) {
return -1;
} else if(this.ind > o.ind) {
return 1;
}
}
return 0;
}
}
public class Main {
static int n;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
Ticket[] tickets = new Ticket[n];
for(int i=0; i<n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int w = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
tickets[i] = new Ticket(i + 1, w * 10000.0 / (10000.0 - q));
}
Arrays.sort(tickets);
StringBuilder sb = new StringBuilder();
for(int i=0; i<n; i++) {
sb.append(tickets[i].ind).append(" ");
}
System.out.println(sb.toString().trim());
}
}