12892 - 생일 선물

정보

• 문제 보기: 12892 - 생일 선물
• 소요 시간: 25분 14초
• 풀이 언어: java
• 체감 난이도: 2️⃣~3️⃣ (2.3)
• 리뷰 횟수: ✅

풀이 키워드

스포주의

투포인터

풀이 코드

정보

• 메모리: 51788 KB
• 시간: 560 ms

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

public class Main
{
    static int n;
    static int d;
    static int[][] プレゼント;
    
	public static void main(String[] args) throws IOException {
		input();
		
		// sort by price asc
	    Arrays.sort(プレゼント, (a, b) -> a[0] - b[0]);
	    
	    // two pointer
	    int i = 0, j = 0;
	    long sum = 0;
	    long mx = 0;
	    while (j < n) {
	        if (プレゼント[j][0] - プレゼント[i][0] < d) {
	            sum += プレゼント[j][1];
	            mx = mx < sum ? sum : mx;
	            ++j;
	        }
	        else { // sorry
	            sum -= プレゼント[i][1];
	            ++i;
	        }
	    }
	    
	    System.out.println(mx);
	}
	
	static void input() throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] line = br.readLine().split(" ");
		n = Integer.parseInt(line[0]);
		d = Integer.parseInt(line[1]);
		
		// init array
		プレゼント = new int[n][2]; // {price, value}
		for (int i = 0; i < n; ++i) {
		    String[] data = br.readLine().split(" "); // shadowing doesn't work
		    プレゼント[i][0] = Integer.parseInt(data[0]);
		    プレゼント[i][1] = Integer.parseInt(data[1]);
		}
	}
}

풀이 해설

사람이 기껏 사왔는데 미안해서 안받는다니 이건 뭔

입력값 범위를 보면 못해도 $O(n\,logn)$의 풀이를 내놓아야 할 것이다.

선물 가격을 기준으로 오름차순 정렬해서 투포인터 스캔하며 계산되는 순간 최대 만족도를 구해두면 된다.

🙆 ㄱㅅ 잘받음

'미안함' 기준에 문제가 없으면 잘 받고 순간 만족도와 최대 만족도를 갱신한다.

if (プレゼント[j][0] - プレゼント[i][0] < d) {
    sum += プレゼント[j][1];
    mx = mx < sum ? sum : mx;
    ++j;
}

🙅 ㅈㅅ 안받음

'미안함'이 트리거되면 이전에 받은것 중 가장 싼마이한걸 돌려준다.

오름차순 정렬이라 가지고 있어봤자 이후 받는 것들도 다 미안함을 트리거하기 때문에 가장 가격이 낮은걸 쳐내는것이다.

결국 비싼걸 받고 싶었다는거네

else { // sorry
    sum -= プレゼント[i][1];
    ++i;
}

메모

• 곧 TIL 쥔장의 생일이라 풀었다. 하지만 문제에서 드러난 강민이의 인성은 쥔장의 인성과 무관하다.
• readLine 쪽에서 변수명 재사용하려 했는데 variable shadowing이 안먹힘. C++보다 기준이 빡셈. (주석으로 표시해둠)