문제 링크
문제
티어: 골드 1
알고리즘: 그리디, 정렬, 우선순위 큐
입력
출력
BOJ에 있는 개의 문제 가운데 개를 풀 때 받아야 하는 틀렸습니다의 최솟값을 출력한다. 개의 문제를 풀 수 없는 경우 -1을 출력한다.
풀이
N개의 문제 가운데 M개를 풀 때 받아야 하는 틀렸습니다의 최솟값을 출력해야 한다.
틀렸습니다를 최소로 받으려면 풀 수 있는 문제 가운데 틀렸습니다를 가장 적게 받을 수 있는 문제를 최우선으로 풀어야 한다.
만약 틀렸습니다를 더 많이 받는 문제를 푼다면, "틀렸습니다." 아에 없이 문제를 풀어 HD, HP를 +1씩 올릴 수 있는 기회를 버리는 경우가 생긴다.
그러면 구현 난이도가 7이고, HP가 4일 때 틀렸습니다. 2개를 받을 것을 3개를 받개 되는 것이다.
그래서 최대한 "틀렸습니다."를 적게 받을 수 있는 문제를 우선적으로 풀어야 한다.
이를 구현하기 위해서는 어떻게 해야될까?
일단 에디토리얼부터 전처리 과정을 진행해 볼 수 있다.
(한별이의 아이디어 능력 x 2 >= 문제의 아이디어 난이도)이 조건이 되어야 에디토리얼을 이해할 수 있는데 이는 에디토리얼이 있기만 하다면 문제의 아이디어 난이도를 줄일 수 있음을 뜻한다.
(한별이의 아이디어 능력 >= 문제의 아이디어 난이도 / 2)와 같이 말이다.
그런데 여기서 중요한 점은 (문제의 아이디어 난이도 / 2)는 소수점을 버리면 안된다. 만약 소수점을 버리면 2 * 2 >= 5가 만족하는 경우가 생겨버린다. 그래서 소수점이 있는 경우에는 +1를 해줘야 한다. 5/2 = 2.5이지만 HD는 정수이기 때문에 3으로 처리해도 상관이 없다.
그리고 에디토리얼을 이해하고 나면 [아이디어 난이도 / 2], [구현 난이도 / 2]로 줄일 수 있는데 여기서 [ ]는 소수점을 버리라는 의미다. 그런데 그냥 전처리 과정에서 아이디어 난이도에 +1를 해주고, 그 아이디어 난이도를 유지해도 상관이 없다.
예를 들어 3 >= 5 / 2 인 경우 3 >= 3 (2.5)이고, 에디토리얼을 이해했기 때문에 문제의 아이디어 난이도는 2가 될 것인데, 어차피 +1한 값보다 한별이의 아이디어 능력은 무조건 크거나 같기 때문에 그대로 유지해도 상관이 없는 것이다.
그래서 다음 예제를 에디토리얼 전처리 과정을 거치면
4 3
3 4 1 0
2 3 0 0
3 6 1 1
1 5 0 1
1 1
전처리 후 에디토리얼은 없어도 됨 (에디토리얼인 경우는 구현 난이도는 /2를 하고 소수점은 버린다.)
4 3
3 4 1
2 3 0
2 3 1
1 2 0
1 1
이 된다.
다음은 이 문제들을 난이도를 기준으로 오름차순 정렬하고, 현재 내 난이도인 HD보다 작거나 같은 모든 문제들을 우선 순위 큐에 넣는다.
여기서 우선 순위 큐에 들어가 있는 문제들은 내가 무조건 풀 수 있는 문제들이며, 정렬 조건은 "틀렸습니다."를 최대한 적게 받는 순이기 때문에
데이터가 있는 경우 (T == 1)를 최우선으로
데이터가 없는 경우끼리 비교는 구현 난이도가 낮은 순으로
정렬 조건을 세우고, 우선 순위 큐에 적용하면 된다.
이후에는 한 문제를 풀고, 또 풀 수 있는 문제를 우선 순위 큐에 넣고, 문제를 풀고, 우선 순위 큐에 넣고..(문제를 풀면 능력치가 올라가기 때문에 전에 불가능했던 문제를 풀 수 있는 가능성이 생김)를 반복해 주면, 최선의 방법으로 문제를 풀기 때문에 가능한지 불가능한지를 알 수 있고, 가능한 경우에는 "틀렸습니다."의 최솟값을 출력할 수 있게 된다.
이 풀이의 시간 복잡도는 O(NlogN)이다.
소스 코드
import java.io.*;
import java.util.*;
class Problem implements Comparable<Problem> {
int d, p, t;
Problem(int d, int p, int t) {
this.d = d;
this.p = p;
this.t = t;
}
@Override
public int compareTo(Problem o) {
if(this.t < o.t) {
return 1;
} else if(this.t > o.t) {
return -1;
} else {
//this.t == o.t
if(this.t == 1) {
return -1;
} else {
//this.t도 0이고, o.t도 0일 때는
//여기서는 구현 난이도가 더 작은 순
if(this.p < o.p) {
return -1;
} else if(this.p > o.p) {
return 1;
}
}
}
return 0;
}
}
public class Main {
static int N, M, HD, HP;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
Problem[] pArr = new Problem[N];
for(int i=0; i<N; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
int d = Integer.parseInt(st2.nextToken());
int p = Integer.parseInt(st2.nextToken());
int t = Integer.parseInt(st2.nextToken());
int e = Integer.parseInt(st2.nextToken());
if(e == 0) {
pArr[i] = new Problem(d, p, t);
} else {
//에디토리얼이 있는 경우는
pArr[i] = new Problem(d / 2 + d % 2, p / 2, t);
}
}
Arrays.sort(pArr, new Comparator<Problem>() {
@Override
public int compare(Problem p1, Problem p2) {
if(p1.d < p2.d) {
return -1;
} else if(p1.d > p2.d) {
return 1;
}
return 0;
}
});
StringTokenizer st3 = new StringTokenizer(br.readLine());
HD = Integer.parseInt(st3.nextToken());
HP = Integer.parseInt(st3.nextToken());
long answer = 0;
boolean isPosible = true;
PriorityQueue<Problem> pq = new PriorityQueue<>();
int nextCursor = 0; //다음 커서 위치
int sol = 0;
while(sol < M) {
//푼 문제가 M보다 작다면
//먼저 풀 수 있는 문제를 넣는다.
for(int i=nextCursor; i<N; i++) {
//다음 커서부터
if(HD < pArr[i].d) {
nextCursor = i;
break;
}
pq.add(pArr[i]);
if(i == N - 1) {
//cursor가 끝까지 도달하면 pq에 모든 문제가 들어갔음을 의미.
nextCursor = N;
}
}
if(pq.isEmpty()) {
//pq가 비어있다면 불가능함.
isPosible = false;
break;
}
//pq가 비어있지 않다면
Problem p = pq.poll();
if(p.t == 0) {
//데이터를 소유하고 있지 않다면
//구현 난이도를 비교해야됨
if(HP < p.p) {
//구현 난이도가 구현 능력보다 높은 경우
answer += p.p - HP;
}
}
sol += 1;
HD += 1;
HP += 1;
}
if(!isPosible) {
System.out.println(-1);
} else {
System.out.println(answer);
}
}
}