[Codeforces #796] B. Patchouli's Magical Talisman

문제 설명

문제 링크
$n$개의 양의 정수가 주어진다.
다음 2가지 행동을 통해서 모든 정수 값을 홀수로 만들려고 할 때 최소한으로 행동한다면 몇 번 행동해야 하는가?

1. 두 개의 정수를 더해서 하나의 정수로 만든다.
2. 하나의 짝수인 정수의 값을 $1/2$한다.

알고리즘

크게 3가지로 나눠서 생각 한 거 같다.

1. 모든 정수가 홀수일 경우
   당연하게도 0번만에 모든 수를 홀수로 만들 수 있다.
2. 모든 정수가 짝수일 경우
   • 모든 짝수를 1번 행동을 통해서 모두 더한 다음에 2번 행동으로 계속 나눠주면 된다.
   • 짝수가 $m$개 있고 횟수는 더할 짝수들을 $2^k$의 배수로 표현한다면 $k$가 가장 작은 수의 $k+m-1$번 걸린다. ($12$, $16$이 있다면 각각 $2^2*3$, $2^4$이고 가장 작은 $k$는 $2$, $\therefore 2+2-1=3$번)
3. 홀수와 짝수가 섞여 있을 경우
   $홀수 + 짝수 = 홀수$를 이용하면 짝수인 수의 수 만큼만 1번 행동을 취하면 모든 수는 홀수가 된다.

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int tc;
int a[200001];
int n;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    // init
    cin >> tc;
 
    for (int tcCnt = 1; tcCnt <= tc; ++tcCnt) {
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
 
        int odd = 0;
        int even = 0;
        int save = INT_MAX;
        for (int i = 1; i <= n; ++i) {
            if (a[i] % 2 == 1) { odd++; continue; }
            even++;
            int cnt = 0;
            while (a[i] % 2 == 0) {
                cnt++;
                a[i] /= 2;
            }
 
            save = min(save, cnt);
        }
 
        if (even == 0) cout << 0 << '\n';
        else if (odd) cout << even << '\n';
        else cout << save + even - 1 << '\n';
 
    }
}

느낀 점...

그냥 저냥 푼 문제