[SWEA] 그래도 수명이 절반이 되어서는... -이진탐색(Binary Search)

그래도 수명이 절반이 되어서는...

이진탐색 구현 자체와 더불어, 해당 조건을 충족하는지 판단하는 방법에 대해 생각해볼 수 있는 문제이다.

배운점

1. N값이 터무니 없이 클 경우에는 이진탐색으로 풀어야하는지 의심하자.

#include <iostream>
using namespace std;
int T,N,K;//테스트케이스,숫자갯수,블록갯수
int arr[200000 + 1];//숫자 모음
int block[200000 + 1];//블록크기 모음

bool isPossible(int target) {
	int index = -1;
	for (int k = 0; k < K; k++) {//몇개의 블록으로 나눌거냐
		for (int b = 0; b < block[k]; b++) {//한 블록의 갯수
			index++;
			if (index == N) return false;
			if (arr[index] > target) {
				k--;
				break;
			}
		}
	}
	return true;
}
int Solve() {
	int s = 0, e = 200000;
	while (s < e) {
		int m = (s + e) / 2;
		if (isPossible(m)) e = m;
		else s = m + 1;
	}

	return e;
}
int main() {
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		scanf("%d %d", &N, &K);
		for (int i = 0; i < N; i++) {
			scanf("%d", &arr[i]);
		}
		for (int i = 0; i < K; i++) {
			scanf("%d", &block[i]);
		}
		int ret=Solve();
		cout << '#' << tc << ' ' << ret << '\n';
	}
	return 0;
}