[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;
}