[백준] 1654.cpp : 랜선 자르기

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

#include <iostream>
#include <vector>

using namespace std;

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

  vector<unsigned int> v;
  v.reserve(10000);

  int n, k;
  cin >> k >> n;
  unsigned int val, max = 0;
  // 최댓값은 구해놓는게 편하다
  for(int i = 0 ; i < k; i++)
  {
    cin >> val;
    if(val > max)
    {
      max = val;
    }
    v.emplace_back(val);
  }

  unsigned int sum = 0;

  unsigned int low = 1;
  unsigned int high = max;
  unsigned int mid = 0;
  // 이분탐색으로 최대 랜선 길이 값에 수렴
  while(low <= high)
  {
    // 중간값을 기준으로 검사한다.
    mid = (low + high) / 2;
     
    for(int i = 0 ; i < k ; i++)
    {
      sum += v[i] / mid;
    }
    // 만약 현재 값이 가능한 숫자라면, 그 위에도 가능한 값이 있을 수 있기 때문에 다시 탐색
    // 최솟값을 현재 값으로 설정
    if(sum >= n)
    {
      low = mid + 1;
    }
    // 아니라면 최댓값을 현재 값으로 설정
    else
    {
      high = mid - 1;
    }
    sum = 0;
  }

  cout << high << '\n';
}

 

[Try]

1. 입력된 랜선들 중 가장 작은 값부터 시작하여 1씩 줄여가며 합을 전부 비교해본다. 완전탐색?

2. 최댓값이 2^31 - 1 이니 int 말고 unsigned int 사용할 것

3. long long

     -> 아니 시간초과가 뜨는게 아니라 틀렸습니다가 뜰 이유가 없는데 왜 저렇게 뜨는지 이해가 안간다 개열받네 진짜

4. 이분탐색 활용. 틀렸습니다.

5. 깨달았다 입력된 랜선들 중 가장 작은 값부터 시작하는 게 틀린 거였다. 굳이 걔를 안잘라도 다른데에서 채워질 수 있으니까...하

 

[Point]

1. 아예 로직에서 착각하고 있는 부분이 있었다. 이분탐색으로 확줄일수 있는 방법 냅두고 완전탐색하면서 조금이라도 줄여보겠다고

     min 부터 시작한 것이 화근이었다.

2. 다들 이분탐색으로 푼 것 같다.

 

[More]