[BOJ] 32894 - 겨율이 좋아

https://www.acmicpc.net/problem/32984

BOJ - 겨울이 좋아

문제 유형: 이진탐색, 매개변수 탐색
문제 난이도: Gold III
시간 제한: 1초
메모리 제한: 1024MB
 

문제

정우는 겨울을 너무 좋아한다. 하지만 아쉽게도 지금은 가을이다. 정우가 사는 도시에는 N그루의 나무가 있고 A번째 나무에는 A_i개의 나뭇잎이 붙어있다. i번째 나무의 나뭇잎은 하루에 Bi개씩 떨어지며, Bi개보다 적게 남아있을 경우에는 전부 떨어진다. 정우는 N그루의 나무에 있는 모든 나뭇잎이 떨어진 날부터를 겨울이라고 부른다.
정우는 특별한 능력을 가지고 있는데, 매일 하나의 나무를 선택해서 그날에 나뭇잎이 2배로 떨어지게 만들 수 있다. 다시 말해서 정우가 i번째 나무를 선택해서 능력을 사용하면 그날 그 나무의 나뭇잎은 2B개 떨어지며, 2Bi개보다 적게 남아있을 경우에는 전부 떨어진다.
나뭇잎이 떨어지기 시작하는 날이 1일째라고 할 때, 정우가 가장 빠르게 겨울이 오도록 능력을 적절히 사용한다면 며칠째에 겨울이 되는지 구해보자.
 

입력

첫 번째 줄에 정우가 사는 도시의 나무의 그루 수 N이 주어진다. (1≤N≤200000)
두 번째 줄에 N개의 정수 A1,A2,…,AN이 공백으로 구분되어 주어진다. Ai번 나무에 붙어있는 나뭇잎의 개수이다. (1≤Ai≤10^9)
세 번째 줄에 N개의 정수 B1,B2,…,BN이 공백으로 구분되어 주어진다. Bi는 i번 나무에 붙어있는 나뭇잎이 하루에 떨어지는 개수이다. (1≤Bi≤10^9)
 

출력

정우가 가장 빠르게 겨울이 오도록 능력을 적절히 사용할 때, 며칠째에 겨울이 되는지 출력한다.
 

풀이

처음에는 우선순위 큐를 이용해서 가장 많이 남은 나무를 밀어주는 시뮬레이션을 얼추 구현했는데.. 이게 정답이 되진 않았다.
 
대신, 이진탐색을 이용해서 최적해를 구하는 것이였다.
정우의 능력을 부스트라 하자.
우선, 하한 l과 상한 h는 다음과 같다: l = 1, h = (부스트 없이 각 나무의 나뭇잎이 떨어지기까지 걸리는 시간들 중 최대값)
l < h인동안, 다음을 반복한다:
 중앙 mid를 구한다. mid날짜만큼 시간이 걸린다고 가정하는 것이다.
 그러고, 각 나무별로 mid날짜가 지나고 나서 추가로 더 필요한 소요 날짜들을 누적한다. 
 만약 그 누적이 mid보다 크다면, mid일동안 부스트로 그 추가도 남은 나무들을 커버할 수 없다.
  즉, 하한을 높여야 한다. l = mid+1로 한다.
 만약 누적이 mid보다 작다면, 부스트를 써서 mid일동안 가능하다는 뜻이다.
  이번에는 상한을 낮춘다. h = mid로 한다.
 
즉, 가능한 lower_bound를 구하는 문제이다.
최종적인 l을 반환해주면 된다.
 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;

  vector<int> a(n), b(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  for (int i = 0; i < n; ++i) {
    cin >> b[i];
  }

  int h = -1;
  for (int i = 0; i < n; ++i) {
    h = max(h, (a[i] + b[i] - 1) / b[i]);
  }
  int l = 1;

  while (l < h) {
    int mid = (l + h) / 2;
    int extra = 0;
    bool flag = true;
    for (int i = 0; i < n; ++i) {
      int fin = (a[i] + b[i] - 1) / b[i];
      if (fin > mid) {
        extra += fin - mid;
        if (extra > mid) {
          flag = false;
          break;
        }
      }
    }
    if (flag) {
      h = mid;
    } else {
      l = mid + 1;
    }
  }

  cout << l << "\n";

  return 0;
}

 
Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

func max(a, b int32) int32 {
	if a > b {
		return a
	}
	return b
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int32
	fmt.Fscan(reader, &n)
	a := make([]int32, n)
	b := make([]int32, n)
	h := int32(-1)
	l := int32(1)
	for i := int32(0); i < n; i++ {
		fmt.Fscan(reader, &a[i])
	}
	for i := int32(0); i < n; i++ {
		fmt.Fscan(reader, &b[i])
		h = max(h, (a[i]+b[i]-1)/b[i])
	}

	for l < h {
		mid := (l + h) / 2
		flag := true
		extra := int32(0)
		for i := int32(0); i < n; i++ {
			fin := (a[i] + b[i] - 1) / b[i]
			if fin > mid {
				extra += fin - mid
				if extra > mid {
					flag = false
					break
				}
			}
		}
		if flag {
			h = mid
		} else {
			l = mid + 1
		}
	}

	fmt.Fprintln(writer, l)
}