문제링크
https://www.acmicpc.net/problem/1781
🛠️ 미해결
- 풀이시간 : 1시간 이상
- 보석도둑 같은 우선순위 큐에서 필요한 거만 빼서 쓰는 문제에 찌들어졌나보다... 날짜 자체를 우선순위 큐로 두고 푸는 문제였다. 날짜를 기준으로 삼아서 그 해당 기간내에서만 길이만큼만 채우고 우선순위 큐의 사이즈가 날짜랑 동일 취급해서 현재의 날짜가 큐의 사이즈를 넘어서면 즉, 데드라인을 벗어나면 지금 필요없는 즉, 가장 낮은 가치 값을 빼버리는 문제였다.
- 왜 생각하지 못했는가? : 말 그대로 우선순위 큐 자체를 날짜로 보지 못하고 해당 필요한 값만 빼서 쓰려고 했다. 왜 우선순위 큐 자체, 즉 사이즈를 날짜로 보고 제외하는 아이디어를 생각하지 못했는가? 현재에서 필요한 것만 남겨두려는 생각은 하였지만 그것을 날짜별로 분리해서 즉, 날짜를 큐의 길이와 동일시 해서 채워나가려는 생각은 하지 못했다. 왜? 남은 것에 대한 고려가 부족했다. 즉, 우선순위 큐를 두 개로 나누어 날짜별 가치별로 나누었었는데 남은 가치를 다루는 큐를 다루려고 하지 못했다. 해당 큐가 중심이었다. 왜? 해당 큐를 중심으로 생각하지 못했는가? 가치가 중심일 때, 제외하는 생각이 부족했다. 즉, 필요한 가치를 빼서 답에 더하려는 생각은 있었지만 전체 가치에서 필요 없는 가치를 제외하는 사고가 부족했다. 왜? 우선순위 큐 문제 자체를 접근하는 생각 차이였던거 같다. 우선순위 큐 문제 자체를 다룰 때 보통 제외시키는 아이디어를 적용시키기 보다는 필요한거만 빼내는 사고로 접근하였기 때문인데 이는 편협적이라는 것을 깨달았다. 우선순위 큐 자체도 정보를 담는 리스트 이고 이 리스트라는 자료구조에서 필요 없는 것을 제외시키고 나머지를 더하는 아이디어 자체를 가지고 있어야 겠다.
결론 : 다음에 접근할 때는? : 최대 가치같은 문제를 고려할 때는, 최대 가치만 빼서 더할 수 있는지를 고려하면서 지금 가장 낮은 가치를 제외할 기준이 있는지도 같이 고려해야 겠다.
🕒 Java 풀이시간: x
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
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());
PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->Integer.compare(a[0],b[0]));
for(int i=0;i<N;i++){
st=new StringTokenizer(br.readLine());
int deadline=Integer.parseInt(st.nextToken());
int cup=Integer.parseInt(st.nextToken());
pq.offer(new int[]{deadline,cup});
}
int answer=0;
PriorityQueue<Integer> pqV=new PriorityQueue<>();
while(!pq.isEmpty()){
int[] now=pq.poll();
int deadline=now[0];
int cup=now[1];
answer+=cup;
pqV.offer(cup);
if(pqV.size()>deadline){
answer-=pqV.poll();
}
}
System.out.println(answer);
}
}이렇게 Java으로 백준의 "컵라면" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
