배경
처음 풀 때에는 이분 탐색 문제인 줄 모르고 덤볐다가 시간 초과로 여러 번 틀렸다.
내가 알던 Binary Search는 ‘이진 탐색’인 것 같았는데 PS 쪽에서는 이분 탐색이라고 하는가보다.
문제 파악
개요
현우라는 친구는 하루에 돈을 1 <= 금액 <= 10,000원 만큼 통장에서 빼서 쓴다고 한다.
통장에서 돈을 인출할 때에는 매번 같은 금액 K만큼만 인출한다.
인출할 때에는 가지고 있던 금액에 더해지는게 아니라, 딱 인출한 돈만 남는다.
예를 들어 오늘 300원을 써야 하는데 손에 200원 밖에 없으면, 200원을 통장에 넣고 500원을 출금하여 500원을 만든다.
현우가 1 <= N <= 100,000일 동안 사용할 돈이 미리 주어졌을 때, 정확히 M번 출금을 하여 먹고 살 수 있도록 하는 가장 작은 K를 구해야 한다.
출금 횟수와 K의 관계
만약 인출액 K가 매우 크다면 단 한번의 출금만으로도 N일 동안 돈을 사용할 수 있을 것이다.
만약 인출액 K가 작다면 출금을 더 자주 해야 할 것이다.
따라서 K와 출금 횟수는 대체로 반비례 하는 것을 알 수 있다.
K의 범위
가장 큰 K는 매일 최대 금액 10,000원씩 100,000일 동안 사용한다고 가정했을 때 필요한 금액인 1,000,000,000(십억)원이다.
K가 아주 작아서 어떤 날에 써야 하는 금액보다 작다면, 그 날에는 돈을 쓸 수 없을 것이다.
그러므로 K는 그 어떤 날에 필요한 돈의 양보다 크거나 같아야 한다.
따라서 K는 max(날마다 필요한 금액의 collection) <= K <= 1,000,000,000 이다.
설계
변수 잡기
변수는 당연히 정답에서 요구하는 K이다.
K는 필요 금액의 최댓값부터 10억 사이에 존재하므로 순차적으로 접근할 수는 없다.
다행히 어떤 K에 대해 출금 횟수를 (빠르게) 세어 M과 비교할 수 있기 때문에 이분 탐색 을 사용하여 O(log n)으로 풀 수 있다.
이분 탐색으로 접근하기
이 문제를 이분 탐색으로 풀 수 있는 이유는, 임의의 K에 대해 그 값이 찾고자 하는 정답보다 작은지 아니면 큰 지 알 수 있기 때문이다.
만약 그렇지 않았다면 모든 경우를 대입해가며 출금 횟수가 M이 되는 경우만 수집한 뒤, 그중에서 K의 최솟값을 찾아야 했을 것이다. 하지만 위에서 언급했듯이 K와 출금 횟수 사이에는 뚜렷한 관계가 있기 때문에 이를 가이드삼아 탐색 범위를 점점 좁혀나갈 수 있다!
너무 어렵게 써놓은 것 같다. 비유하자면 다음과 같다.
이런 상황이 있다:
아주 긴 도로를 따라 1층짜리 단독주택이 수도 없이 길게 늘어서 있고, 그중 한 집에 살고 있는 A라는 사람을 찾아야 한다. 집에 사는 사람이 누구인지 알아내는 유일한 방법은 집 앞에 가서 문을 두드려 물어보는 것이다.
이런 상황에서 순차 탐색을 이용한다면:
- 첫번째 집 문을 두드려 묻는다: - ‘A’씨 계시나요? - ‘아뇨’
- 두 번째 집 문을 두드려 묻는다: -‘A’씨 계시나요? - ‘아뇨’
- 세 번째…
…
만약 집주인들이 착해서 몇 가지 조언을 던져준다면:
- 첫번째 집 문을 두드려 묻는다: - ‘A’씨 계시나요? - ‘아뇨. 왼쪽으로 가봐요.’
- (한참 왼쪽으로 가서) 어느 집 문을 두드려 묻는다: - ‘A’씨 계시나요? - ‘아뇨. 왼쪽으로 가봐요.’
- (또 왼쪽으로 가서) 어느 집 문을 두드려 묻는다: - ‘A’씨 계시나요? - ‘아뇨. 오른쪽으로 가봐요.’
- (적당히 오른쪽으로 가서) 어느 집 문을 두드려 묻는다: - ‘A’씨 계시나요? - ‘아뇨. 왼쪽으로 가봐요.’
- (조금 왼쪽으로 가서) 어느 집 문을 두드려 묻는다: - ‘A’씨 계시나요? - ‘네.’
훨씬 찾기 쉬울 것이다.
이 문제에서는 출금 횟수가 우리를 도와준다.
구현
이진 탐색
일단 이진 탐색의 기본 형태는 아래와 같다:
int left = BLAHBLAH;
int right = FOOBAR;
int mid;
while (left < right) {
mid = left + right / 2;
if (shoud_I_go_right(mid))
left = mid + 1;
else
right = mid;
}
shoud_I_go_right 부분만 만들면 된다.
출금 횟수 구하기
일단 한 번 출금해서 K를 확보한 뒤, 필요한 만큼 쓴다. 한 번 써서 모자라질 것 같으면 잔고를 채운 뒤에 쓴다.
int how_many_withdrawals_are_needed(int withdrawal_unit/* 인출금액 */) {
int count = 1; // 처음 한번은 무조건 출금하고 시작.
int sum = 0; // 한번 출금해서 현재까지 쓴 돈.
for (int i = 0; i < n; ++i) {
if (sum + req[i] > withdrawal_unit) {
// 돈이 부족해지면 출금하고 사용한다.
count++;
sum = req[i];
} else {
// 돈이 남으면 그냥 사용한다.
sum += req[i];
}
}
return count;
}
종합
// N과 M은 각각 n, m에 담김.
// 매일 사용할 돈은 req 배열에 담김.
...
int left = req_max; // req 배열의 최댓값.
int right = 1e9; // 10억.
int mid;
while (left < right) {
if (how_many_withdrawals_are_needed(mid = (left + right) / 2) > m)
left = mid + 1; // 출금이 많이 필요하다는 것을 보니 인출액이 작은 것임. 늘려줌.
else
right = mid; // 출금이 많이 필요하지 않다는 것을 보니 인출액이 큰 것임. 줄여줌.
}
std::cout << left << std::endl;
...
마치며
스승님 감사합니다 :)
댓글