[ARC119 A] 119 × 2^23 + 1

난이도: 69 // 보정 없이는 -417

 

태그

• Brute Force (브루트 포스)
• Mathematics (수학)
• Arithmetic (사칙연산)

 

풀이

1. $b$의 값으로 가능한 수들은?

$b>{\log }_{2}N$이라면, $2^b>2^{{\log }_{2}N}=N$이 됩니다.

즉, $b$의 값으로 가능한 경우는 $O(\log N)$가지가 되겠네요.

 

그러니 가능한 모든 $b$에 대해 답을 구해봅시다.

 

2. $b$가 고정되면, $a,c$로 써야 하는 값은?

$b$가 고정이 되면, 자연스럽게 $2^b$ 역시 고정이 됩니다.

그럼 저희는, $N=a\times 2^b+c$이면서 $a+c$를 최소화하면 되겠네요.

 

$2^b\ge 1$이므로, $a$에 $1$을 더하면 $c$는 $2^b\ge 1$만큼 감소합니다.

그럼 $a$에 $1$을 더했을 때, $a+c$의 합은 그대로거나 감소하게 됩니다.

 

이 아이디어를 잘 적용시키면, $a$를 최대화해야 한다는 결론이 나옵니다.

 

코드

가능한 모든 $b$에 대해, 사용할 수 있는 최대의 $a$를 찾고, 이 때의 $c$를 찾아주면 됩니다.

void Main(){
    ll n; cin >> n;
    ll ans = 2e18;
    ll b = 0, x = n; while (x){
        ll b2 = 1LL<<b;
        if (b2 > n){ break; }
        ll a = n/b2, c = n-a*b2;
        ans = min(ans, a+b+c);
        x >>= 1; b += 1;
    }
    cout << ans;
}