백준 s2 1654 랜선 자르기 c++

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

1654번: 랜선 자르기

 

문제

가지고 있는 K개의 랜선을 잘라 N개를 만들어야 한다.

이때 자른 랜선의 최대 길이는?

 

풀이 (https://blog.encrypted.gg/985)

 

Parametric Search

정의) 조건을 만족하는 최소/최댓값 문제(최적화 문제)를 결정 문제로 변환해 이분탐색을 수행하는 방법

보통은 조건을 이분탐색으로 해서 답을 구하지만, 답의 범위를 이분탐색으로 나누어서 최소/최댓값을 구하는 방법

단, 반드시 그래프가 증가 함수나 감소함수이어야 한다.

 

이 문제에 적용하면, 

원래는 N개의 랜선을 만들 때 최대 길이 X를 구해야하지만 (최적화 문제)

-> 자른 랜선의 길이가 X일 때, N을 만족하는가? (결정 문제)

 

즉, X의 범위 1 ~ (2^31)-1에 이분탐색을 적용하는 것

 

 

풀이

1. 이분 탐색으로 길이 X값 구하기

2. 각각의 X값에 대하여 구한 랜선의 개수가 N보다 크거나 같은지, 작은지 확인

 

조건을 직접 설정해주어야 하므로 STL로는 불가

st = 1
en = 2^31 - 1

while st < en
	res = 길이 x(mid)로 잘랐을 때 나오는 랜선의 개수
    if res < N // 조건 만족 X, X의 길이를 줄여야 나오는 랜선의 개수를 늘릴 수 있음
    	en = mid -1
    else if res >= N // 조건 만족 O, 최대 X를 구해야 하므로 해당 범위부터 다시 탐색
    	st = mid

 

 

+1. 2^31 - 1을 16진수로 나타내기

 

0x8000 0000

여기서 -1을 하면 0x7fff ffff

 

+2. 무한 루프 일어나는 지 확인

직접 이분탐색을 구현할 때는 st, en이 1차이 나는 상황에서 무한 루프가 일어나는지 꼭 테스트해봐야 한다.

해당 코드에서 이분탐색이 일어나는 건 mid가 제대로 설정되지 않아서이다.

 

ex) 

idx	2 (N)	3
	st, mid	en

인 상황에서, 

st = mid 만 계속 되어서 while (st < en) 이 끝나지 않음.

 

mid = (st + en) /2 대신 mid = (st + en + 1)/2로 두어서

mid == en으로 갱신되는 상황을 만들어 줘야 한다.

 

idx	2(N)	3
	st	mid, en

mid값이 en으로 갱신되면, 

다음 loop 때 st = mid로 갱신되므로 st == en이 되어 무사히 while 문이 끝나게 된다.

 

코드

/*boj s2 1654 랜선 자르기*/
#include <iostream>
#define MAXK 10010
using namespace std;

int K, N;
int length[MAXK];

int cut(long long x) {
    int sum = 0;
    for (int k = 0; k < K; k++) {
        sum += length[k] / x;
    }

    return sum;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> K >> N;
    for (int i = 0; i < K; i++)
        cin >> length[i];

    long long st = 1;
    long long en = 0x7fffffff;

    while (st < en) {
        long long x = (st + en + 1) / 2;
        int res = cut(x); // x길이로 잘랐을 때 나오는 N의 개수

        if (res < N) // 만족 X, N을 늘리려면 X를 줄여야 함
            en = x - 1;
        else // 만족 O, 최대 길이를 구해야 하므로 st부터 다시 시작
            st = x;
    }

    cout << st << "\n";
}