백준 1654번: 랜선 자르기

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

1654번: 랜선 자르기

가지고 있는 랜선의 개수와 만드려는 랜선의 개수를 입력받는다.

그 후 가지고 있는 랜선의 길이를 입력받고 그것을 똑같은 길이로 잘라서 랜선의 개수를 맞출 때,

그 길이가 최대가 되게하는 랜선의 길이를 찾는 문제이다.

 

처음에는 랜선의 길이의 평균을 구해고, 각 선이 가지는 비율을 이용해서 문제를 풀려고 했다.

각 (랜선의 길이 / 평균 길이 )를 구해서 그 소수부가 가장 큰 수가 더 많이 나눠질 수  있도록

랜선의 길이를 맞춰주는 것으로 문제를 풀 수 있다고 생각했다.

실제로 예제를 포함해서 많은 반례를 풀었으나 문제 자체를 풀지는 못하였다.

아마도 랜선의 길이를 조절하는 방식이 두루뭉실해서 더 자세한 값은 구하지 못하는 것이라고 생각했다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());
    long prop = 0;
    double[][] arr = new double[N][2];

    for (int i = 0; i < N; i++) {
      arr[i][0] = Integer.parseInt(br.readLine());
      prop += arr[i][0];
    }
    br.close();

    prop /= K;
    while (true) {
      int k = 0;
      for (int i = 0; i < N; i++) {
        arr[i][1] = arr[i][0]/prop - (int)arr[i][0]/prop;
        k += (int)arr[i][0]/prop;
      }
      if (k >= K) break;

      //내림차순
      Arrays.sort(arr, (e1, e2) -> {
        return (e2[1] > e1[1]) ? 1 : -1;
      });

      //prop에는 전선의 길이를 저장
      prop = (int)arr[0][0] / (int)Math.ceil( arr[0][0]/prop );
    }

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write(prop + "\n");
    bw.flush();
    bw.close();
  }
}

반례를 찾아보면서 알게 된 점은 많은 사람들이 이진 탐색으로 문제를 풀었다는 것이다.

그래서 나도 코드를 이진 탐색을 하는 것으로 바꾸기로 하였다.

이진 탐색은 정렬되어 있는 상태에서 특정 수를 찾기 좋은 알고리즘으로

정렬되어 있는 리스트를 반으로 나누었을 때 찾고자 하는 수가 포함된 반은 남기고 그렇지 않은 반은 없애는 방식이다.

그렇게 계속 반 씩 줄여나가다보면 결국 찾고자하는 특정한 수에 도달하게 된다.

 

이진 탐색을 위해 start, mid, end값을 만들어두고 만드려고 하는 랜선의 개수에 맞춰 조건을 만들어 주었다.

계산해서 나온 랜선의 개수가 목표보다 많거나 같다면, 랜선의 길이를 늘려서 그 개수를 줄여야 하므로 아래 반을 없애고,

계산해서 나온 랜선의 개수가 목표보다 적다면, 랜선의 길이를 줄여서 그 개수를 늘려야 하므로 위의 반을 없앴다.

그런 계산 끝에 start와 end가 한 개의 수에서 만나서 start와 end의 크기가 어긋나는 지점에서 반복을 멈추도록 했다.

끝에는 end에 찾고자 하는 랜선의 길이가 들어오게 된다.

왜 start가 아니라 end인지는 확실하지는 않는데, 아마도 코드에서 만든 조건 상 start는 우리가 목표로 한 상태에 도달해도 값이 변하게 설정했기 때문이지 않을까 싶다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());
    int[] binSch = new int[N];

    for (int i = 0; i < N; i++) {
      binSch[i] = Integer.parseInt(br.readLine());
    }
    Arrays.sort(binSch);

    long start = 1;
    long end = binSch[N  - 1];
    while (start <= end) {
      int k = 0;
      long mid = (start + end)/2;
      for (int i: binSch) k += i/mid;
      //k == K면서 가장 큰 값을 찾기...
      if (k >= K) {
        start = ++mid;
      } else /*(k < K)*/ {
        end = --mid;
      }
    }

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write(end + "\n");
    bw.flush();
    bw.close();
  }
}