문제 이해

총 C개의 광물을 캐려고 한다.
이 때 광물을 캐는 방법은 (0,0)에서 (N,M)까지 직사각형을 그려 해당 영역 내의 모든 광물을 캐는 방식으로 진행된다.

C 이하 개수의 광물을 캘 때 최대 가치를 가지도록 캘 수 있는 방법을 구하고, 이 상황에서 최대 가치의 합을 출력하는 문제이다

---

문제 풀이

(x,y) 값이 가정되었다고 생각하자.

이 때 고려할 수 있는 상황은 2가지이다.
1. 영역 내 광물이 C개 이하 존재함
2. 영역 내 광물이 C개보다 많이 존재함

이 두 개 상황을 모두 고려하기 위해 나는 투 포인터를 활용하기로 했다.

x는 0부터 증가하는 방식, y는 100001(출제 제한 값)부터 0까지 감소하는 방식으로 투 포인터를 적용했다.

만약 1번 상황이라고 생각해보자.
나는 더 많은 광물을 캘 수 있다. 캘 수 있는 광물을 많이 하기 위해서는 (x,y) 넓이를 "증가"시켜야 한다. 따라서, x 값을 증가시킬 것이다.

반대로 2번 상황에서는 (x,y) 넓이를 "감소"시켜야 할 것이다.
따라서 y값을 감소시켜 영역 내 초과된 광물 개수를 빼주는 방법을 활용하면 될 것이다.

따라서, 우선순위 큐를 활용했다.
우선순위 큐는 y값을 기준으로 내림차순 정렬되었다.
만약 우선순위 큐 내에 원소 개수가 C개 이하라면 x를 증가시켜 우선순위 큐에 광물을 추가시켰다.
반대로, 우선순위 큐 내에 원소 개수가 C개보다 많다면 y를 감소시켜야 한다.
우리는 우선순위 큐를 활용하고 기준은 y값이 큰 원소부터 제거되기 때문에 맘 편하게 우선순위 큐 내 원소 개수가 C 이하가 될때까지 원소를 제거하면 된다.

여기서 중요한 점은 C개 이하일 때 원소 개수 제거를 종료시키는 것이 아닌 C개 이하가 될 때 같은 y를 가지는 원소들도 모두 제거해야 한다는 점이다.

우리가 원소를 빼는 이유는 "y축의 값"을 감소시켜서 캐는 광물 개수를 줄이는 것이다.
즉, 예를 들어 y=3인 원소를 뺐을 때 C개 이하가 되었다면 우리는 y<3인 영역 내의 광물만 캐야된다는 의미이며, y=3인 원소들을 우선순위 큐에서 모두 제거해야지만 투 포인터를 제대로 활용할 수 있게 되는 것이다.

---

코드

import java.io.*;
import java.util.*;

class Mine implements Comparable<Mine>{
	int x;
	int y;
	long cost;
	
	public Mine(int x, int y, long cost) {
		this.x = x;
		this.y = y;
		this.cost = cost;
	}
	
	@Override
	public int compareTo(Mine m) {
    // y 기준 내림차순 정렬
		return m.y - this.y;
	}
}
public class Main {
	static StringBuilder sb = new StringBuilder();
	
	static int N, C;
	static ArrayList<Mine>[] x_list;
	static ArrayList<Integer> x, y;
    // x : x 좌표들을 오름차순 정렬한 List
    // y : y 좌표들을 내림차순 정렬한 List
	static long value = 0;
	static long ans = 0;
	
	static void search() {
		int x_index = 0;
		int y_index = 0;
		
		PriorityQueue<Mine> queue = new PriorityQueue<>();
		
		int x_pos = 0;
		int y_pos = 100001;
		
		while(true) {
			if(x_index>=x.size()) {
            // 더 이상 x 좌표를 증가시킬 수가 없는 상황
            // y좌표를 꾸준히 감소시켜 C 이하가 되면 그 때 가치를 파악한다
            // C 이하가 될 때 가치를 재면, 이후로 y 좌표를 감소시켜봤자
            // 총 가치는 감소만 하기 때문에 바로 break 시켜주면 된다
				while(true) {
					if(queue.size()<=C) {
						while(true) {
							if(queue.size()!=0 && queue.peek().y==y_pos){
								Mine tmp = queue.poll();
								value-=tmp.cost;
							}
							else {
								break;
							}
						}
						
						break;
					}
					
					Mine tmp = queue.poll();
					value -= tmp.cost;
					y_pos = tmp.y;
				}
				
				ans = Math.max(ans, value);
				break;
			}
			
			if(queue.size()<=C) {
            // C 이하의 광물을 캐는 경우. x 값을 증가시켜 더 많은 광물을 캐자
				x_pos = x.get(x_index);
				
				for(Mine m:x_list[x_pos]) {
					if(m.y >= y_pos) continue;
                    // 우리는 y_pos 미만의 광물만 캐야 한다
                    // 이유 : 투 포인터로 y_pos를 y 좌표 기준으로 삼았기 때문
					
					queue.add(m);
					value += m.cost;
				}
				
				x_index++;
			}
			else {
            // Queue에 C개 이상의 원소가 들어있음
            // y좌표를 감소시켜 캘 수 있는 광물 개수를 줄여야 한다
				while(true) {
					if(queue.size()<=C) {
						while(true) {
                        // Queue 크기가 C 이하가 되었더라도 직전에 뽑은
                        // 광물의 y 높이와 동일한 Mine이라면 삭제해야 한다.
							if(queue.size()!=0 && queue.peek().y==y_pos){
								Mine tmp = queue.poll();
								value-=tmp.cost;
							}
							else {
								break;
							}
						}
                        
						break;
					}
					
					Mine tmp = queue.poll();
					value -= tmp.cost;
					y_pos = tmp.y;
                    // Queue는 우선순위 큐이고, 기준은 y기준 내림차순 정렬
                    // 즉, poll()을 통해 y값이 가장 큰 원소 하나를 큐에서 삭제
				}
			}
			
			if(queue.size()<=C) {
				ans = Math.max(ans, value);
			}
		}
		
		System.out.println(ans);
	}

	public static void main(String[] args) {

		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		C = sc.nextInt();
		
		x_list = new ArrayList[100001];
		HashSet<Integer> x_ = new HashSet<>();
		HashSet<Integer> y_ = new HashSet<>();
		
		for(int i = 0;i<N;i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			long c = sc.nextLong();
			
			if(x_list[x]==null) {
				x_list[x] = new ArrayList<>();
			}
			
			x_list[x].add(new Mine(x,y,c));
			x_.add(x);
			y_.add(y);
		}
		
		x = (new ArrayList<Integer>(x_));
		y = (new ArrayList<Integer>(y_));
		
		Collections.sort(x);
		Collections.reverse(y);
		
		search();
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 시간 초과 : 투 포인터를 활용하지 않고 Brute-Force로 실행했더니 시간 초과가 발생

• 맞았습니다(14/16) : 위에서 말했듯 우선순위 큐에서 y=c인 지점에서 광물 개수가 C 이하가 되었다면 우선순위 큐에서 y=c인 원소를 모두 삭제시키는 추가 과정이 필요하다. 하지만 이 과정을 수행하지 않아 부분 점수가 발생하였다.