백준 c++1654번 랜선 자르기 문제

실패코드

//시간 초과 코드 아무리 시간을 줄이려고 노력해도 이분탐색을 사용하지 않는다면 절대로 풀수 없는 범위가 나오는 문제이다.

#include<iostream>
#include<algorithm>

using namespace std;
int main()
{
        int k,n;
        cin >> k >> n;
        int count, result;
        int *input = new int[k];
        for (int i =0; i < k; i++)
        {
                cin >> input[i];
        }
        count = 0;
        sort(input ,input +k);
        int tk = k;
        for (int i = input[tk-1] ; tk >0; tk--)
        {
                count = 0;
                for (int j = 0; j < k; j++)
                {
                        count +=input[j] / i;
                }
                if (count >= n)
                        break;
        }
        if (count < n)
                tk++;
        int start = input[tk]+input[tk+1]/2;
        count = 0;
        int check = 0;
        for (int i = 0; i < k; i++)
        {
                count+= input[i] / start;
                if (count >=n)
                {
                        check = 1;
                }
        }
        if (check == 1)
        {
                for (int i = input[tk]/2; count >= n; i++)
                {
                        count = 0;
                        for (int j = k-1;  j >=0; j--)
                        {
                                if (input[j] / i == 0)
                                        break;
                                count += input[j] / i;
                                if (count >= n)
                                {
                                        result = i;
                                        break;
                                }
                        }
                }
        }
        else
        {

                for (int i = input[tk]/2; count <n; i--)
                {
                        count = 0;
                        for (int j = k-1;  j >=0; j--)
                        {
                                if (input[j] / i == 0)
                                        break;
                                count += input[j] / i;
                                if (count >= n)
                                {
                                        result = i;
                                        break;
                                }
                        }
                }
        }
        cout << result<< "\n";
        delete []input;
}

#include<iostream>
#include<algorithm>

using namespace std;

int check_result(int *input, int mid,int n,int k)
{
        int count =0;
        for (int i = 0; i <k; i++)
        {
                count += input[i] / mid;
        }
        if (count < n)
                return -1;
        count =0;
        for (int i =0; i < k; i++)
        {
                count += input[i]/(mid +1);
        }
        if (count <n)
                return 1;
        else
                return 0;
}
int main()
{
        long long  k,n,mid;
        cin >> k >> n;
        int *input = new int[k];
        for (int i =0; i < k; i++)
        {
                cin >> input[i];
        }
        sort(input ,input +k);
        long long start = 1;
        long long end = input [k -1];
        while (start <= end)
        {
                mid = (start + end) / 2;
                if (check_result(input,mid,n,k) == 1)
                {
                        cout << mid <<"\n";
                        delete[] input;
                        return (0);
                }
                else if (check_result(input, mid, n, k) == -1)
                {
                        end = mid - 1;
                }
                else
                        start = mid + 1;
        }
        cout << mid << "\n";
        delete[] input;
}

결국 내가 성공한 코드이다.

​

이분탐색 코드의 베이스는

while (start <= end)
{
mid = (start +end) /2
if (target == arr[mid])
return (mid)
else if (target > arr[mid])
start = mid + 1;
else 
end = mid -1;
}

이걸 베이스로 짰었고 이전 취코테에서 공부해놨던 필기가 크게 도움이 됐다. 다음에는 이분탐색을 참고하지 않고 문제

이 글은 코딩 꼬꼬마 시절에 푼 문제를 보관한 글로 네이버에 저장해둔 글을 옮긴 글입니다.
혹시나 참고하시는 부분에 이상한 부분이나 질문이 생긴다면 남겨주시면 친절히 답변 드리겠습니다.