(프로그래머스) 입국심사

문제 링크

• 프로그래머스

요약

• Binary search 를 할 때는 lower bound 와 upper bound 의 차이가 1이 될 때 까지만 좁히자.

최종 §

결과

• 원하는 최종 값을 binary search 로 찾아나가는 과정에서, 후보 시간 내에 각 입국심사대가 몇명의 인원을 처리할 수 있는지를 계산하면 된다.
  • 즉, 해당 시간 내에 처리한 인원이 너무 많으면, 시간이 너무 넉넉하게 할당되었다는 것이기 때문에 시간을 줄여야 하고
  • 반대로 처리한 인원이 너무 적으면 시간이 너무 적게 할당된 것이기에 시간을 늘려야 한다.

#include <string>
#include <vector>
 
using namespace std;
 
#define i64 long long
 
long long solution(int n, vector<int> times) {
	int max_time = 0;
	i64 lowest, highest, goal;
 
	for (int t : times) {
		if (max_time < t) {
			max_time = t;
		}
	}
 
	lowest = 0;
	highest = ((i64)n) * ((i64)max_time);
 
	while (lowest + 1 < highest) {
		i64 left = n;
		goal = (lowest + highest) >> 1;
 
		for (int t : times) {
			left -= goal / ((i64)t);
		}
 
		if (left > 0) {
			lowest = goal;
		} else {
			highest = goal;
		}
	}
 
	return highest;
}

• 디버깅하느라 시간이 좀 걸렸던 것은
  • while (true) 로 돌려서 안에서 break 거는 것 보다 while (low + 1 < high) 로 박아놓는게 생각하기 더 편하다.
  • 또한, 조건은 low + 1 < high 가 되어야 한다. low 와 high 의 차이가 1이 되면 처리하기 귀찮아진다.

다른 코드 (C++) §

코드

#include <string>
#include <vector>
 
using namespace std;
 
long long solution(int n, vector<int> times) {
	long long l = 0, r = n, max = -1, bound = 0, acc = 0, handle = 0;
	for(const auto& el : times) { if(max < el) { max = el; } }
	r *= max;
	while(l <= r) {
		bound = (l + r) / 2;
		acc = 0;
		for(const auto& el : times) {
			acc += bound / el;
		}
		if(acc < n) {
			l = bound + 1;
		} else {
			if(bound <= r) { max = bound; }
			r = bound - 1;
		}
	}
	return max;
}

• 거의 같은 코드이긴 한데, 옛날에 풀었던 것 여기로 옮기기