[Algorithm] 6주차 스터디 - 이분 탐색과 파라메트릭 탐색 (백준 10816, 1654, 2343, 18113)

문제 (10816 : 숫자 카드 2)

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

정수가 하나씩 적혀있는 숫자 카드들이 있다. 상근이가 숫자 카드 N개를 가지고 있다. 또 다른 M개의 숫자 카드가 있는데, 각각의 숫자가 같은 카드를 상근이가 몇 개나 가지고 있는지를 출력하는 문제이다.

풀이

배열을 오름차순으로 정렬한 후, upper_bound(key) - lower_bound(key) 를 이용하면 key 값과 같은 요소의 개수를 바로 찾을 수 있다. 따라서 상근이가 가지고 있는 N개의 카드를 오름차순으로 정렬한 후, 각각 M개의 카드의 숫자가 적힌 카드의 개수를 바로바로 출력한다.

소스코드

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
	int N, M, temp;
	
	scanf("%d", &N); // 숫자 카드 개수 N 입력
	vector<int> v(N); // 숫자 카드 N개를 저장할 배열
	for(int i=0;i<N;i++) // 숫자 카드 N개 입력
		scanf("%d", &v[i]);
	scanf("%d", &M); // 정수 M 입력

	sort(v.begin(), v.end()); // 숫자 카드 정렬
	for(int i=0;i<M;i++){ // M개의 비교할 카드 입력
		// i번째 카드 입력
		scanf("%d", &temp);
		// i번째 카드의 숫자와 같은 카드가 몇 개인지 계산 후 출력
		printf("%d ", upper_bound(v.begin(), v.end(), temp) - lower_bound(v.begin(), v.end(), temp));
	}
	printf("\n");

	return 0;
}

 

문제 (1654 : 랜선 자르기)

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

영식이는 길이가 제각각인 K개의 랜선을 가지고 있고, 이 랜선들을 잘라서 총 N개 이상의 같은 길이의 랜선을 얻고 싶다. 이 때, 가능한 랜선 길이 중 가장 큰 값을 출력하는 문제이다.

풀이

K개의 랜선 길이를 정렬한 후, 이분 탐색을 통해 적절한 랜선 길이를 찾아나가면서, 가장 큰 값을 기억해놓으면 된다. 이 때, "최대"인 값을 구해야 하기 때문에, 이분탐색 시에 양 끝값을 이용해서 중간의 값을 구할 때, 올림 연산(ceil)을 하면 된다.

소스코드

#include <stdio.h>
#include <algorithm>
#include <cmath>

using namespace std;

int K, N; // 현재 가지고 있는 랜선 K개, 필요한 랜선 개수 총 N개
int v[10000]; // 현재 가지고 있는 K개의 랜선 길이
long long ans = 0; // 똑같은 길이 N개를 만들 수 있는 랜선 하나의 최대 길이

// num만큼의 길이로 자르면, 총 몇 개의 랜선을 만들 수 있는지 result 리턴
long long getCounts(int num){
	long long result = 0;
	for(int i=0;i<K;i++){
		result += (v[i] / num); // 각 랜선 길이를 num으로 나눠서 몫을 더함
	}
	return result;
}

int main(){	
	// 입력
	scanf("%d", &K);
	scanf("%d", &N);
	for(int i=0;i<K;i++)
		scanf("%d", &v[i]);
	
	// 정렬
	sort(v, v + K);

	// 이분 탐색
	long long low = 0, high = v[K-1];
	long long mid, tcount;
	while(low <= high){
		mid = ceil((low + high)/2.0); // 이분 탐색 변수 설정
		tcount = getCounts(mid); // mid 를 자르는 랜선 길이의 기준으로 만들었을 때
		if(tcount >= N){ // N개 이상의 랜선을 만들 수 있으면
			ans = max(ans, mid); // 지금까지 나온 답 중에 가장 큰 값을 선택한다.
			low = mid; // 자르는 랜선 길이의 범위을 큰 쪽으로 설정한다.
		}
		else{ // N개 미만의 랜선을 만들 경우
			high = mid-1; // 자르는 랜선 길이의 기준을 작은 쪽으로 설정한다.
		}
	}

	// 출력
	printf("%lld\n", ans);

	return 0;
}

 

문제 (2343 : 기타 레슨)

www.acmicpc.net/problem/2343

2343번: 기타 레슨

강토는 크기가 제각각인 N개의 기타 레슨 동영상을 가지고 있고, 이 동영상들을 M개의 같은 크기의 블루레이에 녹화하려고 한다. 이 때, 기타 레슨 순서는 바뀌면 안되고, 가능한 블루레이의 크기 중에서 가장 작은 값을 출력하는 문제이다.

풀이

이분 탐색을 통해 적절한 블루레이 길이를 찾아나가면서, 가장 작은 값을 기억해놓으면 된다. 이 때, "최소"인 값을 구해야 하기 때문에, 이분탐색 시에 양 끝값을 이용해서 중간의 값을 구할 때, 내림 연산(floor)을 하면 된다.

소스코드

#include <stdio.h>
#include <limits.h>
#include <cmath>
#include <algorithm>

using namespace std;

int N, M; // 총 N개의 레슨, M개의 블루레이
int v[100000]; // N개의 레슨 길이

// 한 블루레이 길이가 length일 때, 몇 개의 블루레이가 필요한지 result 리턴
int getCounts(int length){
	int result = 1;
	int temp = 0; // 현재 블루레이에 들어가있는 레슨의 총 길이
	for(int i=0;i<N;i++){ // N개의 레슨 담기
		if(temp + v[i] > length){ // i번째 레슨을 담지 못하면
			result++; // 블루레이 하나를 추가하고,
			temp = v[i]; // 새로 추가한 블루레이는 i번째 레슨 길이만큼 들어가있다.
		}
		else{ // i번째 레슨을 담을 수 있으면
			temp += v[i]; // i번째 레슨 길이 더해준다.
		}
	}
	return result;
}

int main(){
	// 입력
	scanf("%d", &N);
	scanf("%d", &M);

	int sum = 0;
	for(int i=0;i<N;i++){
		scanf("%d", &v[i]);
		sum += v[i];
	}

	// 이분 탐색
	int low = (*max_element(v, v+N)), high = sum;
	int mid, tcount, ans = sum;
	while(low <= high){
		mid = floor((low + high)/2.0); // 이분 탐색 변수 설정
		tcount = getCounts(mid); // mid 를 한 블루레이 길이의 기준으로 만들었을 때
		if(tcount > M){ // M개 초과의 블루레이가 필요하면
			low = mid + 1; // 한 블루레이 길이를 큰 쪽으로 설정한다.
		}
		else{ // M개 이하의 블루레이가 필요하면
			ans = min(ans, mid); // 지금까지 나온 답 중에 가장 작은 값을 선택한다.
			high = mid; // 한 블루레이의 길이를 작은 쪽으로 설정한다.
		}
	}
	printf("%d\n", ans);

	return 0;
}

 

문제 (18113 : 그르다 김가놈)

www.acmicpc.net/problem/18113

18113번: 그르다 김가놈

김밥 N개가 있다. 먼저, 길이가 K인 꼬다리를 김밥 양쪽에서 잘라내는 작업을 하는데, 김밥의 길이가 2K 이상이면 양쪽 꼬다리를 자르고, K이상이면 한쪽 꼬다리를 자르고, 그보다 짧은 김밥들은 폐기한다. 그 후 손질된 김밥들을 일정한 P 길이 만큼 잘라서 김밥 조각들을 만드는데, 최소 M개를 만들어야 한다. 이때, 가능한 김밥조각의 길이 중 가장 큰 값을 출력하는 문제이다.

풀이

먼저, 김밥 꼬다리를 자르는 작업을 한다. 그 후 이분 탐색을 통해 적절한 김밥조각의 길이를 찾아나가면서, 가능한 값 중에 가장 큰 값을 기억해놓으면 된다.

소스코드

#include <stdio.h>
#include <cmath>
#include <algorithm>

using namespace std;

int N, K, M; // 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M
int L[1000001]; // 김밥의 길이 N개
int ans = -1; //  M조각 이상 만들 수 있는 김밥조각의 길이 P 중의 최대값

// 김밥조각의 길이가 length일 때, 만들 수 있는 김밥조각의 개수 result 리턴
long long getCounts(int length){
	long long result = 0;
	for(int i=0;i<N;i++){
		result += (L[i] / length); // 각 김밥의 길이를 조각의 길이로 나눈 몫을 더함
	}
	return result;
}

int main(){
	// 입력
	scanf("%d", &N);
	scanf("%d", &K);
	scanf("%d", &M);
	for(int i=0;i<N;i++)
		scanf("%d", &L[i]);

	// 김밥 꼬다리 자르기
	for(int i=0;i<N;i++){
		if(L[i] >= 2*K)
			L[i] -= 2*K;
		else if(L[i] > K)
			L[i] -= K;
		else
			L[i] = 0;
	}

	// 이분 탐색
	int low = 1, high = *max_element(L, L+N), mid;
	long long tcount;
	while(low <= high){
		mid = (low + high) >> 1; // 이분 탐색 변수 설정
		tcount = getCounts(mid); // mid 를 자르는 김밥조각 길이의 기준으로 만들었을 때
		if(tcount >= M){ // M개 이상의 김밥조각을 만들 수 있으면
			ans = max(ans, mid); // 지금까지 나온 답 중에 가장 큰 값을 선택한다.
			low = mid + 1; // 자르는 김밥조각 길이의 기준을 큰 쪽으로 설정한다.
		}
		else{ // M개 미만의 김밥조각을 만들 경우
			high = mid - 1; // 자르는 김밥조각의 길이의 기준을 작을 쪽으로 설정한다.
		}
	}
    
	// 출력
	printf("%d\n", ans);

	return 0;
}