[백준 1654번 C/C++] 랜선 자르기

 

 

목차

 

 

---

 

 

[백준 1654번 C/C++] 나이순 정렬

 

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

1654번: 랜선 자르기

---

 

 

해결전략

 

이분탐색, 매개 변수 검색

 

이진 탐색 알고리즘을 사용하여 가능한 가장 긴 랜선 길이를 찾는다.

 

 

---

 

시간초과 - 처음 시도한 코드

 

#include <iostream>
using namespace std;

int k, n, cnt;
long long sum, l;
int kin[10001];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> k >> n;
	for (int i = 0; i < k; i++) {
		cin >> kin[i];
		sum += kin[i];
	}

	l = sum / n;
	
	while(l--)
	{
		cnt = 0;

		for (int i = 0; i < k; i++) 
		{
			int tmp = kin[i];

			while (tmp > l)
			{
				tmp -= l;
				cnt++;
			}	
		}

		if (cnt == n)
		{
			cout << l;
			return 0;
		}
	}

	return 0;
}

시간복잡도(N^2)여서 시간초과가 나온다.

---

 

코드

 

#include <iostream>
using namespace std;

int k, n;
long long maxLength;
long long lo, mid, hi;
long long sum;
long long kin[10001];

long long Cal(long long l) 
{
    long long cnt = 0;
    
    for (int i = 0; i < k; i++) 
    {
        long long temp = kin[i] / l;
        cnt += temp;
    }
    
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> k >> n;

    for (int i = 0; i < k; i++) {
        cin >> kin[i];
        sum += kin[i];
    }

    hi = sum / n;
    lo = 1;

    while (lo <= hi) 
    {
        mid = (lo + hi) / 2;

        if (Cal(mid) >= n) 
        {
            maxLength = mid;
            lo = mid + 1;
        }
        else 
        {
            hi = mid - 1;
        }
    }

    cout << maxLength << endl;

    return 0;
}

 

---

 

더 쉬운 풀이

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, k;
    cin >> k >> n;
    vector<int> v(k);

    for (int i = 0; i < k; i++)
        cin >> v[i];

    long long maxL = *max_element(v.begin(), v.end());
    long long minL = 1;
    long long result = 1;

    while (minL <= maxL)
    {

        long long mid = (minL + maxL) / 2;
        int cnt = 0;

        for (int i : v)
            cnt += i / mid;

        if (cnt >= n)
        {
            minL = mid + 1;
            
            if (mid > result)
                result = mid;
        }
        else
            maxL = mid - 1;
    }

    cout << result;
}

위의 풀이와 원리는 같다. 다만 더 간략화되어 보기 더 편하다.

 

 

이진 탐색을 위한 최대, 최소 값 설정과 결과 변수를 초기화한다.

    long long maxL = *max_element(v.begin(), v.end());
    long long minL = 1;
    long long result = 1;

이진 탐색을 시작한다. minL 과 maxL 이 엇갈리지 않을 때까지 반복한다.

    while (minL <= maxL)
    {

중간 값을 찾고, 랜선의 개수를 카운팅하는 변수를 초기화한다.

        long long mid = (minL + maxL) / 2;
        int cnt = 0;

이진 탐색을 통해 찾은 값으로 랜선 길이를 나누어 몇 개의 랜선이 만들어질 수 있는지 계산한다.

        for (int i : v)
            cnt += i / mid;

만약 만들어진 랜선의 개수가 n 이상이면, 찾은 값을 결과에 저장하고 최소 길이를 갱신한다.

        if (cnt >= n)
        {
            minL = mid + 1;
            
            if (mid > result)
                result = mid;
        }

만약 만들어진 랜선의 개수가 n 미만이면, 최대 길이를 갱신한다.

        else
            maxL = mid - 1;
    }

최종 결과를 출력한다.

    cout << result;
}

 

 

---