[BOJ 1654] 랜선 자르기 C++ 풀이 // 이분 탐색(이진 탐색) 설명

문제 링크

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

랜선 자르기 성공분류

시간 제한 2 초

메모리 제한 128 MB

제출 60448

정답 13186

맞은 사람 8508

비율 20.165%

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 2^31-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

풀이

문제를 천천히 읽어보면, 이분탐색으로 풀 수 있다는 힌트가 있는 문제였습니다.

K개의 랜선을 가지고 있고, 이를 이용해 N개의 랜선을 만드려한다. 단, N개의 랜선의 길이는 모두 같아야한다.

N개의 랜선을 만들 때, 가장 길게 만들 수 있는 랜선의 길이는 얼마인가? 를 구하는 문제입니다.

 

문제를 처음 읽어보셨을 때, 1부터 랜선 최대길이까지 모두 탐색해보면 답이 나오지 않나? 라는 생각이 드셨을겁니다.

그러나 랜선의 길이는 1~2,147,483,647이므로, 너무나 많은 경우가 존재합니다. 이를 위해서 우리는 이분탐색 이라는 탐색 기법을 알아볼 필요가 있습니다.

 

이분탐색 설명

이분 탐색이란? 

이분 탐색(또는 이진탐색, Binary search)이란 말 그대로 탐색할 배열을 반으로 나누어가며 탐색하는 기법입니다.

예시와 함께 설명하겠습니다.

1~9까지 숫자를 가지진 배열이 있다고 가정합시다. 이를 그림으로 표현하면 아래 그림과 같습니다.

 

1~9를 가진 배열

이 배열에서 4이라는 숫자를 찾으려면 어떻게 해야할까요?

단순하게, 처음부터 4이 나올 때 까지 검사할 수도 있습니다.

하지만 배열이 커질수록 탐색 시간이 기하급수적으로 늘어날 것입니다.

이를 빠르게 탐색하는 방법은 없을까요?

만약, 배열이 1~9까지 '정렬'되어 있다면, 우리는 문제를 빠르게 해결할 수 있게 될 것입니다.

 

배열에서 양 끝을 가리키는 포인터와, 양 끝의 중앙을 가리키는 포인터를 놓아봅시다.

이 포인터를 각각 left, right, mid라고 명칭하겠습니다.

1~9를 가진 배열에 3개의 포인터를 놓았다.

이런 상황에서 left와 right의 중간값인 mid가 가리키는 값을 보면, 5를 가리키고 있습니다.

우리가 찾으려는 숫자는 4이므로, 포인터를 적절하게 움직여 수를 탐색할 수 있습니다.

mid가 목표보다 크기 때문에, right를 mid의 근처 위치로 옮겨봅시다.

mid가 목표보다 크기 때문에 right는 mid보다 하나정도 작아도 괜찮을 것입니다.

mid가 목표보다 커, right를 옮겼다.

이 상황에서 mid를 다시 표현해줍시다.

(1+4)/2 = 2.5이므로, 내림하여 2로 표기합시다.

right를 옮긴 후 mid를 다시 표기하였다.

이번에는 mid가 4보다 작습니다. 그렇다면, 이번에는 left를 옮겨봅시다.

mid가 목표보다 작기때문에, left를 mid보다 하나 큰 값에 놓아봅시다.

 

mid가 목표보다 작아, left를 옮겼다.

이 상황에서 mid를 다시 표현해줍시다.

(3+4)/2 = 3.5이므로, 내림하여 3으로 표기합시다.

left를 3으로 옮긴 후, mid를 표기하였다.

이번에도 mid가 목표보다 작습니다.

이 경우는 전과 같이 left를 mid보다 하나 큰 값으로 옮겨봅시다.

mid가 목표보다 작아 left를 옮겼다.

이번에는 공교롭게도, left와 right가 같아졌습니다.

이번에도 mid를 표기해봅시다. (4+4)/2=4이므로, mid는 4가 될 것입니다.

mid가 목표를 찾았다!

드디어 mid가 목표와 같아졌습니다! 이로써 우리는 이분 탐색을 마치게 됩니다.

현재의 예시는 1~9로 숫자가 적어, 이분탐색이 더 복잡하고, 시간도 오래걸려 보일 수 있습니다.

하지만, 1~100억중 88억을 찾는다면, mid는 50억->75억->87억5천만...으로 탐색범위가 급격하게 줄어, 88억을 빠르게 찾을 수 있게 될 것입니다.

 

이분 탐색 아래와 같은 특징을 가집니다.

1. 탐색하려는 배열이 정렬되어 있어야 한다. (=탐색하려는 배열이 단조 증가(1, 2, 3, 4, ...) or 단조 감소(10, 9, 8, 7, ...)를 보여야한다.)

2. 탐색 범위가 1/2씩 줄어드므로 O(logN)의 시간복잡도를 가진다.

 

다시 문제로 돌아가봅시다.

 

문제를 관찰해보면 우리는 중요한 사실을 깨달을 수 있습니다.

바로 가능한 랜선의 길이는 1~최대 랜선 길이만 가능하다는 것, 눈치채셨나요?

가능한 랜선의 길이는 1, 2, 3, 4, ... 의 배열로 나타나며, "단조증가하는 정렬된 배열을 탐색하는 문제" 즉, 이분탐색 문제로 탈바꿈하게 됩니다!

예시 입력	예시 출력
4 11 802 743 457 539	200

예시 입력을 통해 문제를 풀어봅시다.

4개의 랜선을 가지고 있고, 11개로 만들 것이다. 최대 길이는?

위에서의 관찰대로라면, 문제의 답은 1~802중에 있습니다.

우리는 left를 1로 right를 802로 설정하여, mid를 계산한 후, mid가 정답인지를 고려하여, left, right를 적절히 옮길 수 있습니다.

 

그렇다면 mid가 정답인지는 어떻게 고려할까요?

바로, 802, 743, 457, 539를 mid로 나누어, 몫의 합이 11보다 크거나 같은지 검사하면됩니다.

주의할 점은 mid가 11보다 크거나 같다고, 바로 최대값이 나오지 않을 수 있습니다.

따라서,

mid가 11보다 크거나 같다면, left를 mid보다 한 칸 다음으로 옮겨, 가능한지 검사하고 (더 긴 길이로도 11개를 만들 수 있는지?)

mid가 11보다 작다면, right를 mid보다 한 칸 전으로 옮겨, 가능한지 검사하면 됩니다. (더 짧은 길이라면 11개를 만들 수 있는지?)

 

위의 mid가 정답인지 고려하는 것은, 이분 탐색의 핵심이 되는 부분입니다.

처음에는 당연히 접근이 어렵겠지만, 고민과 연습으로 한 단계 더 나아가시길 바랍니다.

 

이렇게 검사하다 보면, left가 right보다 커지는 순간이 올텐데, 이때 검사를 중단하고 답을 출력해주면 됩니다.

 

아래의 코드는 C++로 답을 구현한 코드입니다.

주의할 점은, 랜선의 길이가 INT_MAX인 2,147,483,647까지 가능하므로, 오버플로우가 발생하기 쉽습니다.

이런 경우 데이터 타입을 unsigned int(음수가 없을 때만!) 나 long long의 자료형으로 사용하면 오버플로우를 방지할 수 있습니다.

#include <iostream>
#include <algorithm>

using namespace std;

unsigned int ans;
unsigned int N,K;
unsigned int list[10000];

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	cin >> K >> N;
    
	unsigned int maxi = 0;
    
	for (int i = 0; i < K; i++)
	{
		cin >> list[i];
		maxi = max(maxi, list[i]);
	}

	unsigned int left = 1, right = maxi, mid;
	
	while (left <= right)
	{
		// mid 연산
		mid = (left + right) / 2;
        
		// 몫의 합을 저장하는 변수
		unsigned int now = 0; 
        
		for (int i = 0; i < K; i++)
		{
			//mid로 나눈 몫을 저장
			now += list[i] / mid;
		}

		if (now >= N)
		{
			// 현재 mid로 나눈 값이 N보다 크거나 같다면,
			// left를 움직여 길이가 더 긴 경우는 가능한지 검사
			left = mid + 1;
            
			// N개를 만들 수 있을 때, 답을 더 큰 값으로 계속 갱신
			ans = max(ans, mid);
		}
		else
		{
			// 현재 mid로 나눈 값이 N보다 작다면,
			// right 움직여 길이가 더 짧은 경우는 가능한지 검사
			right = mid - 1;
		}
	}
	
	cout << ans << '\n';
}

 

 

질문과 잘못된 정보 수정 요청은 언제나 환영합니다. 편하게 댓글을 달아주세요.

오늘도 부족한 제 글을 읽어주셔서 감사합니다.