[BOJ] 10025 게으른 백곰 - JAVA

1. 문제

10025번: 게으른 백곰

더운 여름날 동물원의 백곰 앨버트는 너무 더워서 꼼짝도 하기 싫다. 다행히도 사육사들이 앨버트의 더위를 식히기 위해 얼음이 담긴 양동이들을 가져다 주었다. 앨버트가 가장 적은 거리만 움직이고도 최대한 많은 얼음으로 더위를 식힐 수 있도록 도와주자.

우리 안은 1차원 배열로 생각하며, 총 N(1 ≤ N ≤ 100000)개의 얼음 양동이들이 xi(0 ≤ xi ≤ 1,000,000)좌표마다 놓여 있고 각 양동이 안에는 gi(1 ≤ gi ≤ 10,000)씩의 얼음이 들어 있다. 일단 앨버트가 자리를 잡으면 그로부터 좌우로 K(1 ≤ K ≤ 2,000,000) 만큼 떨어진 양동이까지 닿을 수 있다. 앨버트는 양동이가 놓여 있는 자리에도 자리잡을 수 있다. 모든 얼음 양동이의 위치는 다르다.

앨버트가 최적의 자리를 골랐을 때 얼음의 합을 구하시오. 즉, 얼음들의 합의 최댓값을 구해야 한다.

---

2. 풀이

1.  4Byte * 1,000,000 = 4,000,000Byte = 4,000 KB = 4MB이다. 메모리 용량이 충분하기 때문에 1000000칸 배열을 만들어서 얼음 양을 저장한다. 

2.  양동이를 가운데 두고 양옆으로 K만큼 얼음을 가져가기때문에 다르게 생각하면 앞에서부터 2K+1만큼의 얼음을 더한 것과 동일하다.

3.  만약 i-K가 0보다 같거나 크다면 sum에서 ice[i-K]만큼을 뺀다. 이런 조건문이 필요한 이유는 K*2+1<=4,000,001인데, 얼음 위치(i)는 1,000,000이 최대이기 때문이다.

4.  sum에 ice[i]를 더하고, 그 값을 max와 비교해서 더 큰 값을 max에 저장한다.

5.  max를 출력한다.

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

public class BOJ_10025_게으른백곰 {
   public static void main(String[] args) throws Exception {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int K = Integer.parseInt(st.nextToken()) * 2 + 1;

      int[] ice = new int[1000001];
      int g, x;
      for (int i = 0; i < N; i++) {
         st = new StringTokenizer(in.readLine());
         g = Integer.parseInt(st.nextToken());
         x = Integer.parseInt(st.nextToken());
         ice[x] = g;
      }

      int sum = 0, max = 0;
      for (int i = 0; i <= 1000000; i++) {
         if(i-K>=0) sum -= ice[i - K];
         sum += ice[i];
         max = Math.max(max,sum);
      }

      System.out.println(max);
   }
}

---

3. 결과

x는 0부터 시작, N은 1부터 시작인데 그 둘을 혼동해서 여러 번 틀렸다.