백준 - 1654(랜선 자르기) C++

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

1654번: 랜선 자르기

이번 문제는 k개의 랜선을 잘라서 모두 길이가 같은 n개의 랜선으로 만들어야 하는데 이때의 최대 길이를 구하는 문제이다. (n보다 많이 만드는 것도 n개를 만드는 것에 포함된다.)

 

이 문제의 접근 방법은 랜선의 길이를 1부터 가장 긴 랜선의 길이만큼 브루트 포스를 이용해서 구할 수도 있겠지만, 문제를 보면 한 랜선의 최대길이는 2^31 - 1 이하이므로 엄청나게 커 시간 초과가 일어날 것이다.

그래서 이분 탐색을 이용해 접근해 보고자 한다.

 

여기서 low는 1로, high는 k개 랜선 중 가장 길이가 큰 것을 high로 잡는다.

이때 랜선의 길이는 int형의 maximum이므로 low, high의 자료형을 long long으로 해주었다. (mid를 계산할 때 둘을 더하고 2로 나누거나 while 형 조건을 확인할 때 low가 high보다 커질 수 있으므로)

 

이분 탐색 부분 코드이다.

while (low <= high)
  {
    int cnt = 0;
    long long mid = (low + high) / 2;
    for (int i = 0; i < k; i++)
    {
      cnt += arr[i] / mid;
    }
    // 전선 길이 up
    if(cnt >= n){
      if(answer < mid)
        answer = mid;
      low = mid + 1;
    }
    // 전선 길이 down
    else
      high = mid - 1;
  }

 

while문 안에서 초기의 각 랜선의 길이에 접근해 mid로 나눈 몫을 더해준다. (한  기존 랜선당 mid로 나눴을 때 만들어질 수 있는 랜선의 개수)

그 합이 n 이상이라면(문제에서 n보다 많이 만드는 것도 n개를 만드는 것에 포함된다고 하니...),  mid가 기존 답보다 클 경우를 확인해 그 mid가 n개로 나눈 랜선의 최대길이로 업데이트한다.

그리고 더 큰 길이로 랜선을 나누는 것을 시도하기 위해 low = mid + 1로 업데이트한다. (우린 n개 이상으로 나눌 수 있는 최대 랜선의 길이를 구해야 하므로 자를 랜선의 길이를 늘려야 한다.)

 

n보다 작다면, 더 작은 길이로 랜선을 나눠야 하므로 high = mid - 1로 업데이트하며 이를 반복한다. (최대 n개 이상은 만들어야 하므로 자를 랜선의 길이를 줄여야 한다.)

 

전체 코드이다.

#include <bits/stdc++.h>
using namespace std;

int main(){
  int k, n;
  cin >> k >> n;
  int arr[k];
  // 각 랜선들의 길이를 저장
  for (int i = 0; i < k; i++)
    cin >> arr[i];

  long long high = *max_element(arr, arr + k);
  long long low = 1;
  int answer = INT_MIN;
  while (low <= high)
  {
    int cnt = 0;
    long long mid = (low + high) / 2;
    for (int i = 0; i < k; i++)
    {
      cnt += arr[i] / mid;
    }
    // 전선 길이 up
    if(cnt >= n){
      if(answer < mid)
        answer = mid;
      low = mid + 1;
    }
    // 전선 길이 down
    else
      high = mid - 1;
  }
  cout << answer << "\n";
  return 0;
}

 

처음에 자료형을 long long으로 하지 않아 틀렸었다....