[백준(BOJ)] 1654번 : 랜선 자르기 - C++[CPP]

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

1654번: 랜선 자르기

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 이분 탐색
• 매개 변수 탐색

 

---

 

⊙ 문제 접근 과정

 

이분 탐색 알고리즘으로 풀었다. 코드를 짜는 데는 시간이 얼마 걸리지 않았지만 여러 자잘한 애러를 잡아내는데 시간이 더 소요된 문제다.

 

시간 복잡도는 O(N^2)이다. 더 줄이고 싶었지만 아이디어가 생각이 안 났다.

 

max_element를 사용했기 때문에 0을 입력받으면 start도 0 일시 (start+end)가 0이다.

따라서 0으로 나누는 경우도 발생하므로 start 값을 1로 초기화해줬다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <algorithm>

typedef long long ll;
using namespace std;

ll k,n;

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

    ll arr[k];

    for(auto i =0; i<k;i++) {
        cin>> arr[i];
    }

    ll start =1;
    ll end = *max_element(arr,arr+k);
    ll result =0;

    while(start<=end) {
        ll mid=(start+end)/2;
        ll count =0;

        for(auto i=0;i<k;i++) {
            count+=arr[i]/mid;
        }
        if(count<n) {
            end=mid-1;
        } else {
            start = mid +1;
            result=mid;
        }
    }
    cout << result;
}

---

⊙ 결과

 

---

⊙ 마무리

 

혹시 시간복잡도를 더 줄일 수 있다면 댓글로 알려주세요!

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!