BOJ - 17364
BOJ - 17364
(문제 : https://www.acmicpc.net/problem/17364)
UCPC 2021을 준비하면서, 2019 UCPC C번 문제를 풀었음.
먼저 생각한 방법
- 먼저 대회 시작일(s)을 기준으로 오름차순 정렬. s가 같을 경우 e를 기준으로 오름차순 정렬.
- N만큼 정수형 배열(person[])을 선언하여 형섭이가 1등하는 것을 막을 인원이 몇 명인지 확인.
- 1) 만약 person[i]가 0 이상일 경우 end[i]번째보다 작은 start[j]에서 person[j]를 감소시킨다(person[j]--).
2) 만약 person[i]가 0 이라면 형섭이가 참여하여 1등을 하고, e보다 큰 s[j]번을 찾아 다시 3번을 시행한다.- 3 - 1), 3 - 2) 과정을 반복한다.
-> 이렇게 하면 효율적으로 형섭이 1등을 막는 경우가 아님.(종료일과 시작일이 가까울수록 효율적)
문제 해결 방법
- 먼저 대회 종료(e)를 종료일을 기준으로 오름차순 정렬. e가 같을 경우 s를 기준으로 오름차순 정렬.
- treeMap을 선언하여 종료일을 담는 변수를 만듬. (단, K가 1이 아닐 경우.)
(c++에서는 multiSet을 이용하지만, 자바에선 없기때문에 treeMap으로 중복된 값이 있다면 value를 증가.)- 형섭이의 시간을 처음에 0으로 초기화 한 후, 반복문을 통해 0 ~ N - 1까지 start와 end를 비교.
- time >= start일 경우 : 다음 배열 확인(continue)
- time < start일 경우
1) map에서 lowerkey를 못찾았을 경우 형섭이 참여할 수 있으므로, count++ 후 time을 end값으로 변경.
2) map에서 lowerkey를 찾았을 경우 map에서 lowerkey에 해당하는 값을 지우고(key에 대한 value가 1 이상이면 -1, 1이면 remove), map에 end값을 추가(key에 대한 value가 있다면 +1, 없다면 put(end, 1))- 반복문이 끝날때까지 4) ~ 5)를 반복.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class Main {
public static class Node implements Comparable<Node>{
int start;
int end;
Node(int start, int end){
this.start = start;
this.end = end;
}
@Override
public int compareTo(Node o) {
if(o.end != this.end) {
return this.end - o.end;
}
else {
return this.start - o.start;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
Node[] list = new Node[N];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
list[i] = new Node(s, e);
}
Arrays.sort(list);
TreeMap<Integer, Integer> map = new TreeMap<>();
if(K != 1) map.put(0, K - 1);
int count = 0, time = 0;
for(int i = 0; i < N; i++) {
Node curNode = list[i];
int curStart = curNode.start;
int curEnd = curNode.end;
if(time >= curStart) {
continue;
}
if(map.lowerKey(curStart) == null) {
count++;
time = curEnd;
}
else {
int tmp = map.lowerKey(curStart);
if(map.get(tmp) == 1) {
map.remove(tmp);
}
else {
map.put(tmp, map.get(tmp) - 1);
}
if(map.containsKey(curEnd)) {
map.put(curEnd, map.get(curEnd) + 1);
}
else map.put(curEnd, 1);
}
}
System.out.println(count);
}
}
후기
그리디 문제임을 알았지만, 어떤 방식으로 해결해야 최적의 해인지 제대로 몰라서 애먹었음. UCPC 2019 예선 풀이를 참고하여 아이디어를 얻음.
UCPC 2019 예선 풀이.pdf
Author And Source
이 문제에 관하여(BOJ - 17364), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qudgnl0422/BOJ-17364저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)