12892 - 생일 선물

info

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

풀이 키워드

스포주의

투포인터

풀이 코드

info

• 메모리: 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++보다 기준이 빡셈. (주석으로 표시해둠)