백준 15732: 도토리 숨기기

문제 요약

도토리와 상자의 개수가 먼저 주어지고, A번 상자부터 B번 상자까지 C개 간격으로 도토리를 하나씩 보관하는 규칙이 여러 개 주어지면, 마지막 도토리가 들어 있는 상자의 번호를 구하는 문제

문제 분류

• 이분 탐색

문제 풀이

하나하나 그냥 다 세면서 갈 수 있지 않을까? 하다가 도토리 개수의 최대값이 1,000,000,000인걸 보고 바로 포기.

결국 O(n)의 탐색 알고리즘은 사용할 수 없다는 게 되고, 이분 탐색으로 풀어야 한다.

이 문제가 요구하는 마지막 상자의 번호를 이분 탐색하면 되겠다. 이분 탐색에서 사용할 마지막 상자의 번호를 mid라고 할 경우, mid일 때의 도토리 개수는 O(1)로 바로 계산 할 수 있으므로, 이 도토리 갯수와 D를 비교하여 이분 탐색 해 나가면 된다. mid의 도토리 개수가 D보다 많다면 r = mid, 더 적다면 l = mid로 가면 되는 그림. 그렇게 마지막 상자의 번호를 맞춰나가면 된다.

그 도토리 계산 시 생각하지 못한 부분이 있어서 많이 틀렸었다. if문에서 유의하자.

풀이 코드

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

using namespace std;

int main()
{
	int l = 1, r, mid, temp;
	int N, K;
	long long int D, cnt = 0;
	int ary[10000][3];

	cin >> N >> K >> D;
	for (int i = 0; i < K; i++)
		scanf("%d%d%d", &ary[i][0], &ary[i][1], &ary[i][2]);
	r = N;
	while (r >= l) {
		mid = (l + r) / 2;
		cnt = 0;
		for (int i = 0; i < K; i++) {
			temp = min(ary[i][1], mid);
			if (ary[i][0] == temp)
				cnt++;
			else if (ary[i][0] > temp);
			else cnt += (temp - ary[i][0]) / ary[i][2] + 1;
		}
		if (cnt >= D) r = mid - 1;
		else l = mid + 1;
	}
	cout << l;
	return 0;
}