1654 - 랜선 자르기

• 난이도: 실버 2
• 날짜: 2023년 1월 31일
• 상태: Correct
• 추가 검토 여부: Yes

solution

• 이진 탐색을 이용하여 조건을 충족하는 가장 큰 수를 탐색하는 문제이다.
• 이진 탐색 구현 과정에서 입력값에 대한 형을 명확히 설정해야 한다.
  • 초기 코드에서 int를 써서 오버플로우가 발생하였고 이를 long long int로 변경하니 정상 동작하였다.
• 무한 루프에 빠져 시간 초과가 발생하는 경우를 잘 생각해야 한다.
  • step-2의 while문에서 무한 루프가 발생하였다. 양 끝값 모두에 대한 조건을 설정하니 정상 동작하였다.

code

#include <iostream>
using namespace std;

int main()
{
    // input
    int number_of_cable;
    int required_cable;
    cin >> number_of_cable;
    cin >> required_cable;
    int * current_cable_length = new int[number_of_cable];
    for(int i = 0; i < number_of_cable; i++)
        cin >> current_cable_length[i];

    // figure longest cable
    long long int longest_cable_index = 0;
    for(int i = 1; i < number_of_cable; i ++)
        longest_cable_index = (current_cable_length[longest_cable_index] < current_cable_length[i]) ? i : longest_cable_index;
    long long int longest_cable_length = current_cable_length[longest_cable_index];

    // step 1 - set bottom edge
    int piece = 0;
    long long int current_divided_cable = longest_cable_length;
    while(piece < required_cable)
    {
        for(int i = 0; i < number_of_cable; i++)
            piece += current_cable_length[i] / current_divided_cable;
        if(piece < required_cable) 
        {
            current_divided_cable /= 2;
            piece = 0;
        }
    }

    // step 2 - search optimal value from bottom edge to top edge, top edge = bottom edge * 2
    long long int previous_diveded_cable = current_divided_cable * 2;
    long long int middle_value = (previous_diveded_cable + current_divided_cable) / 2;
    piece = 0;
    while((current_divided_cable != middle_value) && (previous_diveded_cable != middle_value))
    {
        for(int i = 0; i < number_of_cable; i++)
            piece += current_cable_length[i] / middle_value;
        if(piece < required_cable)
        {
            previous_diveded_cable = middle_value;
            middle_value = (current_divided_cable + middle_value) / 2;
        }
        else
        {
            current_divided_cable = middle_value;
            middle_value = (middle_value + previous_diveded_cable) / 2;
        }
        piece = 0;
    }

    // print output
    cout << current_divided_cable << endl;

    return 0;
}

ref

1654번: 랜선 자르기