백준 15732 : 도토리 숨기기

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

15732번: 도토리 숨기기

 

다람쥐 문제다. 아니 이분탐색 문제다.

 

구해야 하는 값이 무엇인가? -> 상자의 번호

구해야 하는 값을 기준으로 결정문제로 만들 수 있는가? -> Yes

=> 이분탐색!

 

여기서 결정문제라 함은, 예-아니오로 대답할 수 있는 문제다.

프로그래밍 관점에서 보자면 true, false로 나눌 수 있는 문제를 말하고, 이 문제의 경우 정답이 되는 특정 상자의 번호를 기준으로 앞쪽은 전부 조건을 만족하지 못하는 false 상태, 뒤쪽은 조건을 만족하는 true 상태로 나뉘므로 결정문제다.

 

로직 및 근거는 아래와 같다.

 

1. 정답 상자가 A라고 할 때(A에 마지막 도토리가 담겼을 때), A보다 뒤에 있는 상자 위치에서 넣을 수 있는 도토리 수를 계산하면 당연히 최대 도토리 수 D보다 크거나 같은 개수의 도토리를 수용할 수 있으므로 모든 도토리를 담을 수 있다.

2. 정답 상자가 A라고 할 때, A보다 앞에 있는 상자 위치에서 넣을 수 있는 도토리 수를 계산하면 당연히 최대 도토리의 수 D보다 작다.

3. 상자 번호 0부터 N까지를 초기 범위로 하여 상자 번호를 기준으로 이분탐색을 돌면서 해당 상자 위치에서 모든 도토리를 담을 수 있는지 체크한다.

4. 현재 담을 수 있는 도토리의 수는 규칙들을 순회하면서 담을 수 있는 도토리 수를 더해주는 방법으로 구한다.

 

코드로 구현하면 아래와 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Area { int A, B, C; };
vector<Area> v;

void solution() {
	int N, K, D, A, B, C;
	Area tmp;

	cin >> N >> K >> D;

	while (K--) {
		cin >> A >> B >> C;
		tmp.A = A, tmp.B = B, tmp.C = C;
		v.emplace_back(tmp);
	}

	int lo = 0, hi = N, mid, sum;
	while (lo + 1 < hi) {
		sum = 0;
		mid = (lo + hi) / 2;
		for (int i = 0; i < v.size(); i++) {
			// 규칙 시작 위치가 현재 mid위치보다 더 크다면 이 규칙으로 인해 담기는 도토리는 없다.
			if (v[i].A > mid) continue;
			// 규칙 끝 위치와 현재 mid위치 중 작은 값을 끝 위치로 하여 담기는 도토리를 계산한다.
			sum += (min(v[i].B, mid) - v[i].A) / v[i].C + 1;
			// sum이 D와 크거나 같아지는 순간 더이상의 연산은 의미없기 때문에 break해준다. 이건 해줘도 되고 안해줘도 된다.
			if (sum >= D) break;
		}

		if (sum >= D) hi = mid;
		else lo = mid;
	}
	// while문을 빠져나왔을 때, lo는 마지막 false값을, hi는 첫 번째 true값을 가리키고 있다.
	cout << hi << '\n';
}

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

	return 0;
}

메모리: 2528 kb

시간: 4 ms