COFO::1426C Increase and Copy

• Link : COFO::1426C

Problem

• level : 1100
• tag : binary search, constructive algorithms, math

Point

• 최초에 배열 a에 1 하나만 포함되어있고, 매 순간 두 가지 중 하나의 작업을 진행할 수 있습니다.
  • 작업 1 : a에 포함된 원소의 값을 1 증가시킵니다.
  • 작업 2 : a에 포함된 원소하나를 복사해서 a배열에 붙여넣습니다.
• x번의 operation을 통해서, a배열의 합이 n이상이 되도록 하고 싶습니다.
• n이 주어질때 최소값 x를 출력합니다.

Design

• 역발상을 하지 못해서 editorial을 참고하여 문제를 풀었습니다.
• 다음 사항들은 문제에 나온 예제를 몇번 손으로 써보면 파악할 수 있습니다.
  • 작업 1과 작업 2가 혼재되어있는 경우가 있을 수 있지만,
  • 결론적으로 작업 1을 연속적으로 진행하고 작업 2를 연속적으로 진행하는 것과 똑같습니다.
• 따라서, 작업 1을 먼저 진행 후 작업 2를 진행하면 됩니다.
• 저는 작업의 수가 주어질때 만들 수 있는 최대 수를 생각하는 방향으로 생각했었습니다.
• 하지만, 문제에서 요청하는 건 수가 주어졌을때 최소 작업의 수를 계산하라는 것이었고, 이 간극의 역발상을 해내지 못했습니다.
• 거꾸로 생각해보면 충분히 생각해볼 수 있었을텐데 말입니다.
• 서론이 길었고 풀이는 다음과 같습니다.
  • n을 만드려고 합니다.
  • 최초에 1이 주어집니다.
  • 작업 1을 (x-1)번 진행해서 x가 되었습니다.
  • 이제 x를 y번 복사하면 x * (y+1) 이 되고, 이 값이 n이상이 되어야 합니다.
  • 즉, x * (y+1) >= n
  • 따라서, y >= (n-x)/x 이죠
  • 그럼 이때 사용되는 총 작업의 수를 y의 부등호를 무시하고 계산해보면 다음과 같습니다.
  • count = (x-1) + (n-x)/x
  • 이제 여기서 무시한 y의 부등호를 처리해주어야 합니다.
  • 즉 정확히 저희는 아래와 같은 값을 도출해내야 합니다.
  • count = (x-1) + ceil( (n-x)/x )
  • (n-x)/x의 반올림된 값을 구해야 하죠
  • 이 값은 다음과 같습니다.
  • ((n-x) + x-1)/x
  • 뒤에 더한 (x-1)/x 에 주목할 필요가 있습니다.
  • (n-x)/x 를 반올림 해주어야 하는 경우는, (n-x) % x != 0 인 경우밖에 없습니다.
  • 즉, 분자에 1이상인 값이 있는 경우이고 이를 위해 x-1을 분자에 더해주면 이게 반올림이 되는 것이죠
• 풀이는 위와 같고, 아쉽게도 한가지 이유를 파악하지 못한 점이 있습니다.
• 왜 루트(n)까지만 돌리면 답을 찾을 수 있는지 입니다.
  • 이유를 찾게되면 추가하도록 하겠습니다.

Big O(time)

• O(logN)

Code

// https://beenpow.github.io/
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define r_rep(i,a,b) for(int i=(a);i>(b);i--)
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
typedef long long ll;
using namespace std;
ll n;
void solve(){
    cin >> n;
    ll ans = 1e9;
    for(int x = 1; x * x <= n; x++){
        //ans = min(ans, (x-1) + (n-x) /x ); 1번
        ans = min(ans, (x-1) + ((n-x) + x -1)/x ); // 2번
    }
    cout << ans << '\n';
}
int main(){
    //freopen("input.txt", "r", stdin);
    int tc; cin >> tc;
    while(tc--)
        solve();
    return 0;
}