[백준/BOJ] 1654 랜선 자르기 (C ++)

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	248681	59634	40307	21.596%

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 2^31 - 1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

예제 입력 1

4 11
802
743
457
539

예제 출력 1

200

힌트

802cm 랜선에서 4개, 743cm 랜선에서 3개, 457cm 랜선에서 2개, 539cm 랜선에서 2개를 잘라내 모두 11개를 만들 수 있다.

풀이

해당 문제 같은 경우에는 이분 탐색으로 풀 수 있습니다. 다만 평범한 이분 탐색과는 다르게 전체 배열에 있는 길이를 잘라 최대로 큰 값을 남겨야 하는 문제입니다.

값을 배열에 넣는 과정에서 가장 큰 값을 구해줍니다. 우리가 찾고자 하는 범위는 최소 값인 1부터 가장 큰 값인 최대 값까지 일 것입니다. 그래서 찾고자 하는 범위는 1부터 최대 값 까지의 내에 있을 것입니다.

찾고자 하는 범위의 절반 값을 이용해 각 배열의 각 값을 나누면, 각 값에서 만들 수 있는 최대의 랜선 개수가 나올 것입니다. (300 / 140 = 2 .. 20 -> 2개를 만들고 20cm가 남는다는 뜻이기 때문에)

세어준 개수가 최대 개수를 넘는다면 절반 기준 오른쪽을 탐색하면 될 것이고(길이를 늘려줘야 개수가 감소하기 때문에)
최대 개수보다 모자라다면 왼쪽을 탐색하며 개수를 맞춰주면 됩니다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
  ios_base::sync_with_stdio(0); 
  cin.tie(NULL); cout.tie(NULL);

  int k, n, cnt;
  int max_len = -1;
  cin >> k >> n;

  vector<int> vec(k);
  for(int i = 0 ; i < k ; i++){
    cin >> vec[i];
    max_len = max(max_len, vec[i]);
  }

  long long start = 1;
  long long end = max_len;
  long long mid = (start + end) / 2;

  while(start <= end){
    cnt = 0;

    for(int i = 0 ; i < k ; i++){
      cnt += vec[i] / mid;
    }

    if(cnt >= n){
      start = mid + 1;
    }
    else{
      end = mid - 1;
    }
    mid = (start + end) / 2;

  }

  cout << mid;

  return 0;
}

리뷰

이분 탐색의 응용 문제를 풀어보았습니다. 해당 알고리즘은 매개 변수 탐색(Parametric search) 이라고 합니다. 매개 변수 탐색은 최적화 문제를 결정 문제로 바꾸어 풀 때 사용합니다.

여기서 최적화 문제란 어떤 알고리즘의 최적 솔루션을 찾는 것이고, 결정 문제란 답이 이미 결정되어 있다고 보고 문제를 푸는 것

매개 변수 탐색과 이분 탐색의 다른 점은 이분 탐색은 목표한 값을 찾으면 코드를 종료하고, 매개 변수 탐색은 값을 찾아도 배열 전체를 찾아봅니다. 

---

추가로 랜선의 길이 조건을 보지 못해서 계속해서 int 자료형을 선언해서 시간초과가 계속 났습니다. 문제를 더 잘 읽는 습관을 들이는 것이 중요할 것 같습니다.

성능