백준 2343번 기타 레슨

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

전형적인 이분탐색 문제였습니다.

high를 곡들의 길이 합으로 두고 mid를 최대 녹음 시간이라고 가정했을 때 성립하는지 여부를 판단하면 되는 문제였습니다.

#include <iostream>

#include <algorithm>

#include <climits>

using namespace std;

 

const int MAX = 100000;

 

int N, M;

int blueray[MAX];

 

bool func(int mid)

{

        int sum = 0;

        //블루레이 수

        int num = 1;

 

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

        {

                 //곡 하나가 최대 녹음시간보다 길 수 없습니다.

                 if (blueray[i] > mid)

                         return false;

 

                 sum += blueray[i];

                 if (sum > mid)

                 {

                         sum = blueray[i];

                         num++;

                 }

        }

 

        return M >= num;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

        int sum = 0;

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

        {

                 cin >> blueray[i];

 

                 sum += blueray[i];

        }

 

        int low = 1, high = sum;

        int result = 0;

        while (low <= high)

        {

                 int mid = (low + high) / 2;

                 //mid는 최대 녹음 시간

                 if (func(mid))

                 {

                         result = mid;

                         high = mid - 1;

                 }

                 else

                         low = mid + 1;

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

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