백준 1654번 랜선 자르기

문제 링크입니다: https://www.acmicpc.net/problem/1654

이분 탐색을 이용하는 문제에 익숙하지 않다고 판단해서 풀어본 문제입니다.

알고리즘은 아래와 같습니다.

1. 입력 받은 전선의 길이 중 최대 길이를 high로 잡습니다.

2. 자르는 전선의 길이가 존재해야하므로 low는 1로 잡습니다.

3. 이분 탐색을 진행하면서 mid에 대해 조건을 충족하는지 확인합니다.

i) 조건이 충족된다면 자르는 전선의 길이를 늘립니다.

ii) 조건이 충족되지 않는다면 자른는 전선의 길이를 줄입니다.

4. 조건이 충족되는 최대 길이를 출력합니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 10000;

 

int N, M;

long long electricLine[MAX];

 

bool possible(long long len)

{

        int cnt = 0;

        for (int i = 0; i < N; i++)

                 cnt += electricLine[i] / len;

       

        //조건 충족 여부

        if (cnt >= M)

                 return true;

        return false;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

        long long high = 0;

        for (int i = 0; i < N; i++)

        {

                 cin >> electricLine[i];

 

                 high = max(high, electricLine[i]);

        }

 

        long long result = 0;

        long long low = 1;

 

        //이분 탐색 진행

        while (low <= high)

        {

                 long long mid = (low + high) / 2;

                 if (possible(mid))

                 {

                         if (result < mid)

                                 result = mid;

                         low = mid + 1;

                 }

                 else

                         high = mid - 1;

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~