문제 링크
문제
2220년에도 “2220 신촌지역 대학생 프로그래밍 대회 동아리 연합 수시 대회”가 성공적으로 개최된다. SUAPC은 이제 모든 학생이 즐길 수 있도록 다양한 난이도의 대회가 1년에 수시로 열리며, 상금 규모는 억대가 되었다. 이런 미래를 예측한 연두는 냉동인간이 되어 폐관수련을 통해 알고리즘만 공부하였으며, 이제 모든 대회에서 반드시 1등을 한다.
하지만 각 대회마다 참가자격이 생겨 모든 대회에 참가하지 못할 수도 있다! 상금의 독식을 막기 위해 대회마다 “상금 상한”이 존재하며, 어떤 대회를 참가하기 전까지 모은 상금의 합이 그 대회의 상금 상한을 초과한다면 그 대회는 참가할 수 없다. 대회가 열리는 순서는 정해져 있고 대회들의 시간은 겹치지 않는다.
올해 열리는 N개의 대회에 모두 참가하여 상금을 쓸어 모을 계획을 세웠던 연두는 이 사실을 알고 큰 충격을 받았다. 대회를 하나까지 참가하지 못하는 것은 참을 수 있지만, 2개 이상의 대회를 참가할 수 없다면 절망에 빠져 500년을 더 냉동인간 상태로 지낼 것이다. 아직 손이 덜 해동된 연두를 위하여, 올해 연두가 적어도 N-1개의 대회에 참가할 수 있는지 여러분이 대신 확인해주자.
입력
첫 번째 줄에 올해 열리는 대회의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
다음 N개의 줄에 i번째 대회에 대한 정보인 정수 xi, pi가 대회가 열리는 순서대로 주어진다. (1 ≤ xi, pi ≤ 109). 이는 i번째 대회에 참가하기 전까지 모은 상금의 합이 xi원 이하여야 이 대회에 참가할 수 있고, 이 대회에 참가하면 연두가 얻는 상금이 pi원임을 의미한다.
출력
만약 올해 연두가 최소 N − 1개의 대회에 참가할 수 있으면 Kkeo-eok을, 참가할 수 없으면 Zzz를 출력한다.
풀이
올해 연두가 적어도 N-1개의 대회에 참가할 수 있는지 구하는 문제다.
특정 대회 하나만 제외해서 모든 대회에 참가할 수 있어야 하는데,
어떤 대회를 제외해야 모든 대회에 참가할 수 있는 확률이 가장 높아질까?
대회를 하나씩 제외해 본다면 쉽게 답을 구할 수 있지만, N은 최대 100,000이기 때문에 이 풀이는 불가능하다.
잘 생각해보면, 순서대로 대회에 참가해 상금을 챙겨가면서, 어느 순간 대회에 참가하지 못하는 상황이 발생한다. 이 상황에서는 무조건 특정 대회를 제외시켜야 한다. 이때 최선의 판단을 내려야 확률을 최상으로 높일 수 있다.
선택지는 두 가지다. 현재 대회를 제외할 것인지, 이전 대회 중 하나를 제외할 것인지
선택지 중 어떤 대회를 제외해야 할까? 대회에 참가 확률을 높인다는 것은 뭘까?
그것은 현재 얻은 상금을 최소화하는 것이다. 왜냐하면 모든 대회에 조건은 현재 내가 얻은 상금이 적을수록 만족할 확률이 높아지기 때문이다.
그러면 선택지 중 어떤 대회를 제외할 것인지 기준은 상금이 큰 대회다.
이때 주의할 점은 상금이 큰 대회가 이전 대회일 때 그 대회에 상금을 제외해도 현재 대회에 조건을 만족하지 않을 수 있다. 이 경우에는 현재 대회를 제외하는 선택지밖에 없기 때문에 현재 대회를 제외해 준다.
그리디 알고리즘 풀이는 시간 복잡도 O(N)이다.
소스 코드
import java.io.*;
import java.util.*;
class Competition {
int x, p;
Competition(int x, int p) {
this.x = x;
this.p = p;
}
}
public class Main {
static int N;
static Competition[] competitions;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
competitions = new Competition[N];
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
competitions[i] = new Competition(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
System.out.println(start());
}
static String start() {
boolean ep = false; //제외했는지
long sum = 0; //상금 총합
int max = -1; //상금
for(int i=0; i<N; i++) {
if(sum <= competitions[i].x) {
sum += competitions[i].p;
max = Math.max(competitions[i].p, max);
} else {
//x원 이하가 아님
if(ep) {
//이미 제외를 한 경우 || 대회를 제외해도 더 큰 경우
return "Zzz";
}
if((sum - max) <= competitions[i].x) {
//이전 대회를 제외했을 때 조건을 만족한다면
//현재 대회와 이전 대회 중 상금을 비교해서 더 큰 상금을 제외해준다.
if(max > competitions[i].p) {
//이전 대회 상금이 더 크다면
sum -= max;
sum += competitions[i].p;
}
}
//이전 대회르 제외했을 때도 조건을 만족하지 않는다면 현재 대회를 제외한다.
ep = true;
}
}
return "Kkeo-eok";
}
}