[백준] 1654번 랜선 자르기 (C++) - binary search

문제

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

1654번: 랜선 자르기

코드

#include <iostream>
#include <vector>

using namespace std;

int main(){
  int k, n;
  cin >> k >> n;

  int max = 0;
  vector<int> v;
  for(int i=0; i<k; i++){
    int a;
    cin >> a;
    v.push_back(a);
    if(a > max){
      max = a;
    }
  }
  
  long long start = 1;
  long long end = max;
  long long result;
  while(start <= end){
    long long sum = 0;
    long long mid = (start+end)/2;
    for(int h : v){
      sum += h/mid;
    }
    if(sum >= n){
      start = mid+1;
      result = mid;
    } else{
      end = mid-1;
    }
  }
  cout << result;
  return 0;
}

정리

저번에 푼 2805번과 매우 유사한 유형의 문제이다.

2805번과 같이 이 문제도 이진 탐색으로 접근을 해서 문제를 풀었다.

그러나 58%까지 성공하더니 '틀렸습니다'가 나왔다.

그 이유는 바로 자료형 범위 때문이었다.

랜선의 길이가 2^31-1 이하의 자연수이기 때문에 int형 범위에 딱 알맞다고 생각해서 처음에는 sum만 long long형으로 바꾸어 다시 제출했다. 그러나 또 '틀렸습니다'가 나왔다.

start, end, mid 모두 long long으로 선언해야 문제가 풀린다. 정확한 이유는 모르겠지만 일단 앞으로 문제 풀 때는 int형 범위에 다 들어간다 하더라도 일단 범위가 크면 안전하게 long long으로 선언해야 겠다.

참조

https://kdongree.tistory.com/40

https://hunidev.tistory.com/16