BOJ 1654 : 랜선자르기 - C++
랜선자르기
코드
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
ll N,M,high;
vector<ll> arr;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
{
int a;
cin >> a;
arr.push_back(a);
high=max(high,arr[i]);
}
/* left가 0이면 N=1,K=1, input=1 일 때 나누는 수인 mid가 0이되어서
런타임 에러가 발생한다 */
ll left=1, right=high;
ll ans=0;
while(left<=right)
{
ll tot = 0;
ll mid = (left + right)/2;
for(auto a : arr)
tot += a/mid; // 항상 mid가 0이되는 예외가 없는지 확인해줘야 함
if(tot < M)
right = mid - 1;
else
/* tot이 M보다 크거나 같을때 일단 지금까지 랜선 길이를 저장하고
더 큰값을 검사하러 이동 */
{
ans = max(ans,mid);
left = mid + 1;
}
}
cout << ans;
return 0;
}
- 로직
: 최적의 랜선 길이
를 찾는 탐색을 이분탐색
으로 하여 찾는다
- 주의
: 이분탐색
을 할 때 항상 나누는 수
인 mid
가 0이되는 경우
를 찾아 예외처리
를 해주어야 한다
(본 문제
: N=1, M=1, input=1
일 때 mid
가 0
이되므로 최초left
를 1
로 초기화)
Author And Source
이 문제에 관하여(BOJ 1654 : 랜선자르기 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-1654-랜선자르기-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <cstdio> #include <vector> #include <queue> #include <iostream> #include <cmath> #include <algorithm> #define ll long long using namespace std; ll N,M,high; vector<ll> arr; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M; for(int i=0;i<N;i++) { int a; cin >> a; arr.push_back(a); high=max(high,arr[i]); } /* left가 0이면 N=1,K=1, input=1 일 때 나누는 수인 mid가 0이되어서 런타임 에러가 발생한다 */ ll left=1, right=high; ll ans=0; while(left<=right) { ll tot = 0; ll mid = (left + right)/2; for(auto a : arr) tot += a/mid; // 항상 mid가 0이되는 예외가 없는지 확인해줘야 함 if(tot < M) right = mid - 1; else /* tot이 M보다 크거나 같을때 일단 지금까지 랜선 길이를 저장하고 더 큰값을 검사하러 이동 */ { ans = max(ans,mid); left = mid + 1; } } cout << ans; return 0; }
- 로직
:최적의 랜선 길이
를 찾는 탐색을이분탐색
으로 하여 찾는다- 주의
:이분탐색
을 할 때 항상나누는 수
인mid
가0이되는 경우
를 찾아예외처리
를 해주어야 한다
(본 문제
:N=1, M=1, input=1
일 때mid
가0
이되므로최초left
를1
로 초기화)
Author And Source
이 문제에 관하여(BOJ 1654 : 랜선자르기 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-1654-랜선자르기-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)