이진탐색 문제 (백준1654번)

개요

늘 심심하면 진행하는 백준 문제풀이 시간입니다.

오늘은 백준 1654번 랜선자르기 문제를 풀어보려 합니다. 정답율이 21.7% 라 왠지 승부욕을 자극하는군요. 😅

백준 단계별로 풀어보기 ➡️ 이분탐색 3번 문제입니다.

랜선자르기문제

아래는 문제 설명입니다.

출처 : 백준

정답은 아래와 같이 출력해야합니다.

출처 : 백준

풀이 과정

일단 처음은 문제가 잘 이해되지 않아 2번 정독해 읽어보았습니다.

기존 보유한 K개의 랜선을 활용해 필요한 N개의 랜선을 만들 수 있는 최대 길이를 구하는 문제입니다.

예를 들면 랜선 4개를 가지고 있는데 그 길이가 각각 802,743,457,539 입니다.

위 랜선들을 잘라서 11개의 새로운 랜선을 만들려고 하는데 만들수 있는 11개 랜선의 최대 길이는 얼마인가? 를 답해야 합니다.

1. 첫 시도

모든 랜선의 길이를 더하고 평균을 구한 후, 기존 케이블들에서 평균 값을 나누어 갯수를 구해가다 N개 이상이면 답이 아닐까?

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

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

    int k,n;
    cin >> k >> n;

    vector<unsigned int> v(k);

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

    unsigned long long total = std::accumulate(v.begin(), v.end(),0);
    unsigned long long avg = total/n;

    while (true)
    {
        unsigned long long cnt=0;
        for(auto& i:v)
            cnt += i/avg;

        if(cnt>=n)
        {
            cout << avg << '\n';
            break;
        }
        avg-=1;
    }
    return 0;
}

평균을 구하고 1씩 줄여가며 N개의 갯수를 만족하는 길이는 순차탐색하는 방식입니다.

전체 선을 합한 총길이는 2541이고 11로 나누면 하나의 랜선 길이가 231 이지만 기존에 보유한 4개 랜선을 잘라서 이어 붙이는 것은 불가능하므로 231에서 1을 뺀 230, 229, 228 등 시도해 가다보면 11개를 만족하는 최대 길이는 200입니다.

답은 잘 나오지만 시간 초과가 나왔습니다.

시간초과를 해결하기 위한 방법을 한참 고민해봤지만 해결책이 잘 떠오르지 않는데, 이진탐색을 이용해 풀어야 하는 문제라고 자꾸 되뇌어 봅니다.

2. 두번째 시도

이진 탐색을 시도해 봅니다.

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

unsigned long long bSearch(int right, const vector<unsigned int>& v, int k, int n)
{
    unsigned int left = 1;
    unsigned int mid, cnt;
    
    while(left<=right)
    {
        cnt = 0;
        mid = (left+right) / 2;
        
        for(int i=0; i<k; i++)
            cnt += v[i]/mid;
        
        if(left==right)
        {
            if(cnt<n)
                return left-1;
            else
                return left;
        }
        else
        {
            if(cnt<n)
                right = mid;
            else
                left = mid+1;
        }
    }
    return 0;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    
    int k,n;
    cin >> k >> n;
    
    vector<unsigned int> v(k);    
    unsigned long long max = 0;
    
    for(int i=0; i<k; i++)
    {
        cin >> v[i];        
        if(max<v[i])
            max = v[i];
    }
    cout << bSearch(max, v, k, n) << '\n';
    return 0;
}

와우 시간제한을 만족합니다.

1. mid 값을 정하고 cnt를 계산

2. cnt<n 이면, mid가 크다는 의미 right를 줄이자

3. cnt>=n 이면, mid를 키워도 되므로 left를 늘리자

4. 이진 탐색이 끝나는 시점 (left == right) 에 값을 반환

5. 이때 cnt<n이면, 현재 left로 n개를 만들수 없으므로 left-1반환

6. 아니면 cnt>=n 이므로 left반환

잘 이해가지 않는다면 바이너리서치 함수에 중단점(Break Point)을 설정하고 디버깅 해보면 금방 이해가 됩니다.

C++로 제출 후 아래는 파이썬으로 풀어본 코드입니다.

import sys

def bSearch(right, lst, k, n):
    left = 1

    while left<=right:
        cnt = 0
        mid = (left+right)//2

        for i in range(k):
            cnt += lst[i]//mid

        if left==right:
            if cnt<n:
                return left-1
            else:
                return left
        else:
            if cnt<n:
                right = mid
            else:
                left = mid+1
    return 0

k, n = map(int, input().split(' '))

lst = []
m = 0
for i in range(k):
    c = int(sys.stdin.readline().rstrip())
    lst.append(c)    
    if m<c:
        m = c

# print(lst)
# print(m)

print(bSearch(m, lst, k, n))

감사합니다.

이 블로그 검색

오션코딩학원