Educational Codeforces Round 116 - B. Update Files

문제 설명

버클리 음대에는 새 운영체제를 위한 업데이트 파일을 받았다. 처음에 이 파일은 $1$번째 컴퓨터에만 설치되어 있다.

업데이트 파일은 모든 $n$개 컴퓨터에 설치되어야 하는데, 컴퓨터는 인터넷에 연결되어 있지 않기 때문에 케이블을 이용해서 컴퓨터끼리 케이블을 연결해서 업데이트 파일을 받아야 한다. 오직 한 컴퓨터에는 한 케이블만 연결 될 수 있다. 따라서 업데이트 파일이 설치되어있는 컴퓨터가 다른 컴퓨터에 케이블로 연결되어서 업데이트 파일을 전송하는데 정확히 한시간이 걸린다.

우리가 해야할 일은 만약 버클리음대에 케이블이 $k$개 밖에 없는 상태에서 $n$개 컴퓨터가 모두 패치파일을 받기 위해서 걸리는 최소 시간을 구하는 것이다.

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 10^5)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 컴퓨터의 수와 패치 케이블의 수를 나타내는 정수 $n$과 $k (1 \le k \le n \e 10^{18})$ 이 주어진다.

Output
모든 $n$개 컴퓨터가 업데이트 파일을 전부 받기 위해서 걸리는 최소 시간을 의미하는 정수를 출력한다.

Example
input
4
8 3
6 6
7 1
1 1

output
4
3
6
0

문제 접근

사용한 알고리즘: 구현, 수학, 그리디 알고리즘
걸린 시간 : 00:05
이 문제는 1시간이 흐른후, 2시간이 흐른후, 3시간이 흐른후... 이런식으로 그림을 그려서 연결된 컴퓨터의 수를 계산해보면 쉽게 규칙을 찾을 수 있다. 그리고 거기에 빠른 구현이 더해지면 빨리 풀것 같은데 구현이 조금 느려서 약 30분만에 accept한 문제이다.

처음에 컴퓨터는 1대부터 시작되고, 한 컴퓨터에 한 대를 연결하니 그 다음 시간에는 컴퓨터 2대가 완료된다. 그리고 컴퓨터 2대에 다른 컴퓨터 2대를 연결하니 그 다음 시간에는 컴퓨터 4대가 완료된다. 왜 최대로 컴퓨터를 연결하냐면 모든 컴퓨터에 파일을 업데이트 하기 위해서 걸리는 최소 시간을 구해야하기 때문이다. 이것이 그리디 알고리즘을 사용한 것이라고 할 수 있다. 즉 컴퓨터가 완료되는 변화수는 $1, 2, 4, 8, 16, ...$ 으로 앞에 숫자에 2를 곱한 것으로 규칙이 정해진다.

그런데 여기서 문제가 생긴다. 이 대학교에는 최대 $k$개의 케이블만 존재하기 때문에 만약 케이블이 3개 밖에 없다면 4에서 8로 넘어갈 때 4대 모두 케이블을 연결 할 수 없으므로 4대 다음에는 7대의 컴퓨터만 업데이트가 완료된다. 즉 정상적으로 늘어나는 컴퓨터의 수를 $cur$이라고 하면 $cur > k$ 인 경우 그 이후로는 $k$개 씩만 늘어나게 된다. 그렇기 때문에 처음으로 $cur > k$가 되는 구간을 찾는 것이 이 문제의 목표이고 그것을 구현한게 아래 코드의 while문이다.

만약 $cur < k$인데 모든 컴퓨터를 다 완료하지 못했다면 남은 컴퓨터는 $k$개씩 업데이트가 차례로 완료하기 때문에 $(n - cur)$에 $k$를 나눠주는 추가적인 연산이 필요하다. 여기서 codeforces의 well-known 방식이 나오는데, 우리는 $4, 5, 6$을 $3$으로 나눈 값을 모두 2로 만들고 싶다. 왜냐하면 4는 3개 컴퓨터가 연결되고 나서 컴퓨터가 1대 남으니 1시간이 더 필요하고, 5는 3개 컴퓨터가 연결되고 나서 2개 컴퓨터가 남으니 추가적으로 한시간이 더 걸린다. 그런데 컴퓨터에서는 정수끼리 나눗셈에서는 버림을 취하기 때문에 $4/3$을 하면 원하는 답인 2가 아니라 1이 나온다. 그래서 여기서 $k - 1$을 더한 다음에 $k$를 나누게 되면 $4$가 $6$으로, $5$가 $7$으로, $6$이 $8$로 바뀌게 되서 모두 원하는 답인 2가 나오게 된다. 이 방식을 모든 오렌지 레드 코더들이 사용해서 나도 익혀보려고 한다.

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        ll n, k; cin >> n >> k;
        ll cur = 1, res = 0;
        while(cur < k){
            cur *= 2;
            res++;
        }
        if(cur < n) res += (n - cur + k - 1) / k;
        cout << res << "\n";
    }
    return 0;
}