개요

백준 15732번: 도토리 숨기기

• 입력
  첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 B번 상자까지 C개 간격으로 도토리를 하나씩 넣는 규칙을 뜻한다. D는 모든 규칙으로 넣을 수 있는 도토리의 수보다 같거나 작다.

• 출력
  D개의 도토리를 규칙에 맞게 상자 앞에서부터 넣었을 때 마지막 도토리가 들어가는 상자의 번호를 출력하시오.

접근 방식

1. 제일 간단한 접근 방식으로 생각했다.
   모든 입력값들을 받아서 정렬 해놓고 몇번째 상자인지 구하는 방법이다.
   -> 당연히 안된다 최대 상자 갯수가 100만개, 규칙이 최대 1만개이므로,
   곱하면 원소 갯수가 100억이 나온다.
   평균적으로 1초에 10억번의 연산을 하므로 최소 10초정도 이상 걸릴것이므로 시간초과다.

2. 이분탐색으로 마지막 상자의 번호를 구하는 방식을 사용했다.
   원리는 마지막 상자의 번호로 mid값을 준다.
   각각의 규칙에서 mid값의 상자가 몇번째인지를 구한 후 모든 값을 다 더했을 때
   입력값으로 받은 도토리값보다 같거나 크면 high값을 낮추고
   도토리값보다 작다면 low값을 올린다.

3. 상자를 직접 하나하나 반복문으로 돌릴 순 없으므로(시간)
   상자의 갯수를 구할때 쓴 식은 (상자의 마지막 번호- 상자의 첫 번호) / 상자의 규칙 +1이다.
   사용하게되면 해당 규칙에서 마지막 번호까지의 상자의 갯수가 나온다.
   -> 여기서 내가 한 첫 번째 실수는 상자의 마지막번호가 상자의 첫 번호보다 작게 되면
   음수를 계산하게 되어서 오답이 나온다!
   -> 이 부분에서 상자의 번호를 무시하고 도토리를 입력값대로 넣을 수 있는 수를 뱉어내서
   해당 수와 최대한 가까운 상자를 찾으려고

	/// <summary>
	/// 매개로 들어온 num값보다 작은 박스 번호 중 num과 제일 가까운 box return
	/// </summary>
	/// <param name="num"></param>
	/// <returns></returns>
	long long nearestNumberBox(long long num) {
		long long ret = 0, tmp = 0;;
		for (int i = 0; i < K; i++) {
			// 해당 규칙에서 num보다 작은 상자 구하고 
			if (num >= v[i].startBox) {
				tmp = v[i].startBox + ((num - v[i].startBox) / v[i].rule) * v[i].rule;
				//num과의 차이가 ret이 더 작다면 ret유지, tmp가 더 작다면 ret=tmp로 갱신
				ret = (num - ret) >= (num - tmp) ? tmp : ret;
			}
		}
		return ret;
	}

이런 함수까지 만들었었다.. 음수만 안 나오게 짰다면 바로 해당 상자번호가 나왔을 텐데..

4. 두 번째 실수는
   마지막 상자의 번호로 넣어준 mid값이 각 규칙의 마지막 상자 번호보다 작은지 체크해야한다.
   이 부분을 간과했더니
   200 2 6
   10 40 10
   80 100 10
   위와 같은 testcase에서 진짜 답은 90번이지만 답이 60으로 나온다.
   60이 나오는 이유는 첫번째 규칙에서 넣을 수 있는 도토리 수를 10~60까지 6개라고 계산하고,
   두번째 규칙에서 도토리를 아무 곳에도 못 넣으므로 총 6개 넣을 수 있다! 라고 판단해버리는 것이다.
   이 실수 찾아내는 데 좀 많은 검색과 고민의 시간을 들였다...

코드

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

	using namespace std;
	int N, K, D;

	//세 가지 값 입력받을 구조체
	struct inputS {
		int startBox;
		int endBox;
		int rule;
	};

	vector<inputS> v;

	//입력함수
	void input() {
		inputS iS;
		cin >> N >> K >> D;
		int temp1, temp2, temp3;
		for (int i = 0; i < K; i++) {
			cin >> temp1 >> temp2 >> temp3;
			iS = { temp1,temp2,temp3 };
			v.push_back(iS);
		}
	}
	/// <summary>
	/// 들어온 mid값이 마지막이라고 했을 때, 도토리가 남거나 같으면 false를 return해서 high값을 조절,
	/// 도토리 부족하면 true를 return해 low값을 조정 
	/// </summary>
	/// <param name="mid"></param>
	/// <returns></returns>
	bool checkIfLastAcornBox(int mid) {
		long long tmpSum = 0,tmp=0;
		for (int i = 0; i < K; i++) {
			//이 부분을 빼먹을시 규칙의 끝번호가 마지막 상자보다 크다면 해당 규칙에선 넣을 수 있는 상자의 갯수가 더 크게 나온다.
			tmp = min(v[i].endBox, mid);
			//tmp가 첫 상자의 번호보다 작으면 tmpSum에 음수를 더해줘서 이상한 값이 조건에 안 걸리고 답으로 나옴!
			if (tmp >= v[i].startBox) {
				tmpSum += ((tmp - v[i].startBox) / v[i].rule) + 1;

			}
			//총 도토리 갯수보다 넣을 도토리 갯수가 많아지면 false return해서 high값 조절
			if (tmpSum >= D) return false;
		}
		//반복문 다 통과했다면 true를 return해서 low값 조절
		return true;
	
	}

	void solution() {
		int low=0, high=1'000'000'001, mid=0;
		while (low + 1 < high) {
			mid = (low + high) / 2;
			((checkIfLastAcornBox(mid)) ? low : high) = mid;
		}
		cout<<high;
	
	}

	int main() {
		input();
		solution();
	}

문풀후생

각 규칙에서 mid값이 첫 번째 박스보다 커야한다는 조건과
mid값이 마지막 박스보다 크다면 마지막 박스값을 가지고 상자갯수를 구해야하는 조건을
간과해서 너무 시간을 많이 들인 문제였다.

하지만 또 많은 시간을 들이고 고민을 많이 한 덕분에
문제를 풀때 각각 조건에 대해서 더 고민해봐야겠다는 생각이 기억에 박힌 것 같다.
얻은게 많은 문제였다.