boj13397 구간 나누기_java

링크

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

문제

N개의 수로 이루어진 1차원 배열이 있다. 이 배열을 M개 이하의 구간으로 나누어서 구간의 점수의 최댓값을 최소로 하려고 한다. 구간은 다음과 같은 조건을 만족해야 한다.

1. 하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다.
2. 배열의 각 수는 모두 하나의 구간에 포함되어 있어야 한다.

구간의 점수란 구간에 속한 수의 최댓값과 최솟값의 차이이다.

예를 들어, 배열이 [1, 5, 4, 6, 2, 1, 3, 7] 이고, M = 3인 경우가 있다.

이때, [1, 5], [4, 6, 2], [1, 3, 7]로 구간을 나누면 각 구간의 점수는 4, 4, 6점이 된다. 이때, 최댓값은 6점이다.

만약, [1, 5, 4], [6, 2, 1], [3, 7]로 구간을 나누었다면, 각 구간의 점수는 4, 5, 4점이 되고, 이때 최댓값은 5점이 된다.

두 경우 중에서 최댓값이 최소인 것은 5점인 것이고, 5점보다 최댓값을 작게 만드는 방법은 없다.

배열과 M이 주어졌을 때, 구간의 점수의 최댓값의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N)

둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 구간의 점수의 최댓값의 최솟값을 출력한다.

나의 풀이

• 두가지 단계로 풀이하였다.
  • 첫번째, NxN 배열에 계산 결과 값 넣기
    • i가 행, j가 열 이라고 했을때, i행 위치부터 j까지의 범위에서 가장큰값-가장작은 값 의 결과값을 prefix[i][j]에 넣어주었다.
  • 두번째, answer에 들어가야 하는 값을 0부터 크기 N 배열의 최댓값-최솟값 의 범위안에서 이진탐색을 하고, 0~M의 범위안에서 이것이 만들어질 수 있는지 가장 뒷자리수 부터 체크하며 연산을 진행한다.
• 핵심 코드

  while(M>1&&left<=right){
      int mid = (left+right)/2;
      maxValue= 0;
      int cnt = 0;
      for (int i = N-1; i >=0;) {
          if(cnt>M) break;
          cnt+=1;
          int j = i;
  
          while(j>=0){
              if(prefix[j][i]>mid){
                  if(i!=j){
                      maxValue = Math.max(maxValue,prefix[j+1][i]);
                      break;
                  }
              }
              j-=1;
          }
          i=j;
      }
      if(cnt<=M){
          answer = Math.min(answer,mid);
          right = mid - 1;
      }else{
          left = mid+1;
      }
  }
  

• 전체 코드

  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.StringTokenizer;
  
  public class boj13397 {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
  
          int N = Integer.parseInt(st.nextToken());
          int M = Integer.parseInt(st.nextToken());
          int[] nums = new int[N];
          int answer = Integer.MAX_VALUE;
          st = new StringTokenizer(br.readLine());
          for (int i = 0; i < N; i++) {
              nums[i] = Integer.parseInt(st.nextToken());
          }
  
          int[][] prefix = new int[N][N];
  
          for (int i = 0; i < N; i++) {
              int max = nums[i];
              int min = nums[i];
              for (int j = i; j < N; j++) {
                  if (i==j){
                      prefix[i][j] = nums[i];
                  }else{
                      if(nums[j]>max){
                          max = nums[j];
                      }else if(nums[j]<min){
                          min = nums[j];
                      }
                      prefix[i][j] = max-min;
                  }
              }
          }
  
          int[] sorted = Arrays.stream(nums).sorted().toArray();
          int left = 0;
          int right = sorted[N-1]-sorted[0];
          int maxValue = 0;
          answer = right;
          while(M>1&&left<=right){
              int mid = (left+right)/2;
              maxValue= 0;
              int cnt = 0;
              for (int i = N-1; i >=0;) {
                  if(cnt>M) break;
                  cnt+=1;
                  int j = i;
  
                  while(j>=0){
                      if(prefix[j][i]>mid){
                          if(i!=j){
                              maxValue = Math.max(maxValue,prefix[j+1][i]);
                              break;
                          }
                      }
                      j-=1;
                  }
                  i=j;
              }
              if(cnt<=M){
                  answer = Math.min(answer,mid);
                  right = mid - 1;
              }else{
                  left = mid+1;
              }
          }
  
          System.out.println(answer);
      }
  }

결과