BOJ 1654 - 랜선 자르기
알고리즘/이분 탐색문제
https://www.acmicpc.net/problem/1654
풀이
처음으로 푼 이분 탐색 문제다. 항상 랜선을 자를수 있는 경우의 입력만 들어온다 가정하고 left를 1로, right를 가장 큰 랜선의 길이로 정한 뒤 입력받은 모든 랜선들을 mid 값(left+right를 2로 나눈 값)으로 나눈 몫을 변수에 더하고 만약 필요한 랜선의 갯수보다 같거나 많다면 ans 변수에 값을 넣고 가장 마지막에 ans 변수에 들어가있는 값을 출력하게 했다.
#include <stdio.h> #define max(a,b) a>b?a:b int main(){ long long n,m[10000]={0},k,d,i,left=1,right=-1,mid,ans; scanf("%lld%lld",&n,&k); for(i=0;i<n;i++){ scanf("%lld",&m[i]); right=max(right,m[i]); } while(left<=right){ mid=(left+right)/2; d=0; for(i=0;i<n;i++) d+=m[i]/mid; if(d >= k){ ans = mid; left = mid+1; }else{ right = mid-1; } } printf("%lld",ans); }
주의할 점
1. mid값으로 모든 랜선을 나눈 몫의 합이 K(필요한 랜선의 갯수)를 넘어가는 경우에도 답이 될 수 있다. 처음 제출때 이 부분을 간과하고 있다가 틀렸다.