[Codeforces][Round #701][Div.2] A : Add and Divide (C++)

https://codeforces.com/contest/1485/problem/A

Problem - A - Codeforces

 

 

[난이도] Div.2
[유형] 수학

[풀이]
아이디어 : +와 / 연산을 사용할 때 +연산을 먼저 하는게 무조건 이득이다.

1. b,b+1,b+2,b+3...b+i 를 검사 (+를 몇개 쓸건지..)
2. '/'가 영향력이 더 크기때문에 +를 많이 써서 b를 크게 만들수록 연산의 횟수는 점점 줄어들 것이다.
그러나 일정 이상 b가 커지면 b를 더이상 증가시키는 것이 손해인 순간이 온다 (ex a=12,b=7 : a=12,b=8 의 결과는 동일하다.)

3. 그러므로 b를 증가시키는 것이 손해가 되는 순간이 i일 때,
정답은 i-1만큼 b를 증가시켰을때이다.

 

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int tc,a,b;
 
int sol(int a,int b){
    int ret=0;
    while(a!=0){
        a/=b;
        ret++;
    }
    return ret;
}
 
int main(){
    scanf("%d",&tc);
    while(tc--){
        int ans=1e8;
 
        scanf("%d%d",&a,&b);
 
        int prev=1e8;
        for(int i=0;;i++){
            if(b+i==1) continue;
 
            int t = sol(a,b+i);
            t+=i;
            if(t>prev) break;
            prev=t;
        }
        printf("%d\n",prev);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round701-Div.2/A.cpp