[백준, BOJ 10025] 게으른 백곰 (java)
Problem Solving/BOJ

[백준, BOJ 10025] 게으른 백곰 (java)

728x90

https://www.acmicpc.net/problem/10025

메모리: 44,580 KB , 시간: 448 ms

사용 알고리즘: 두 포인터

728x90

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
// ice[i][0] := 얼음의 양
// ice[i][1] := 양동이 좌표
int[][] ice = new int[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
ice[i][0] = Integer.parseInt(st.nextToken());
ice[i][1] = Integer.parseInt(st.nextToken());
}
// 양동이 좌표 기준으로 오름차순 정렬
Arrays.sort(ice, (o1, o2) -> o1[1] - o2[1]);
// 투 포인터
int s = 0, e = 0;
int sum = ice[0][0];
int result = 0;
while(e < N) {
// s와 e 사이의 양동이가 자리잡을 수 있는 범위 내라면
if(ice[e][1] - ice[s][1] <= 2 * K) {
result = Math.max(result, sum);
if(++e < N) sum += ice[e][0];
}
// s와 e 사이의 양동이가 자리잡을 수 있는 범위를 초과했다면
else {
sum -= ice[s++][0];
}
}
System.out.println(result);
}
}

 

728x90