(BOJ) 15732 도토리 숨기기

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

 

문제 풀이:

 

1. A,B,C 입력 받음

수형이는 A번 상자부터 B번 상자까지 C개 간격으로 도토리를 하나씩 더 넣는 규칙을 만들었다

-> vector<pair<pair<int,int>,int>> v에 넣는다  // {{처음 상자,끝 상자}, 간격}

 

2. 이분 탐색

현재 위치(mid)까지의 도토리 개수를 구하고 도토리 개수보다 많은지 적은지 비교

	int l = 0, r = 1000000;
	while (l < r) {
		int mid = (l + r) >> 1;
		int t = 0;
		for (int i = 0; i < v.size(); i++) {
			if (t > k) break;
			else if (v[i].first.first > mid) continue;
			if (v[i].first.second < mid) {
				t += (v[i].first.second - v[i].first.first) / v[i].second+1;
			}
			else t += (mid-v[i].first.first) / v[i].second+1;
		}

		if (t >= k) r = mid;
		else l = mid + 1;
	}

 지금 보고 있는 규칙의 시작이 현재 위치보다 다음이라면 continue;

 지금 보고 있는 규칙이 현재 위치보다 먼저 끝난다면 '(규칙 끝-규칙 시작)/(규칙 간격)+1'만큼 더하고

 현재 위치보다 나중에 끝난다면 '(현재 위치-규칙 시작)/(규칙 간격)+1'만큼 더함

 이 합이 원하는 도토리 개수보다 많다면 r=mid를 통해 지금보다 앞에 있는 상자를 보고

 적다면 l=mid+1을 통해 더 뒤에 있는 상자를 봄

 

 if(t==k)라고 바로 break 해버리, 도토리가 있는 마지막 상자 위치가 아니라 그 이상의 값 출력 가능하므로 주의!

 

 

소스 코드:

#include <iostream>
#include <vector>
#include <algorithm>
#define sz 1000001
using namespace std;

typedef pair<int, int> P;
int n, m,k;

vector<pair<P, int>> v;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		int q, w, e;
		cin >> q >> w >> e;
		v.push_back({ {q,w},e });
	}
	int l = 0, r = 1000000;
	while (l < r) {
		int mid = (l + r) >> 1;
		int t = 0;
		for (int i = 0; i < v.size(); i++) {
			if (t > k) break;
			else if (v[i].first.first > mid) continue;
			if (v[i].first.second < mid) {
				t += (v[i].first.second - v[i].first.first) / v[i].second+1;
			}
			else t += (mid-v[i].first.first) / v[i].second+1;
		}

		if (t >= k) r = mid;
		else l = mid + 1;
	}
	cout << l << '\n';
	return 0;
}