Codeforces #1490A Dense Array

문제

https://codeforces.com/problemset/problem/1490/A

걸린 시간

00 : 37 : 43

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> a(n);
        for(auto& i : a) cin >> i;
        int ans = 0;
        for(int i = 0; i < n-1; i++){
            float val = (float)max(a[i], a[i+1]) / (float)min(a[i], a[i+1]);
            while(val > 2){
                val /= 2;
                ans++;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

배열 a 에서 두개의 인접한 요소가 다음과 같은 조건을 만족시킬 때 밀집하다고 한다.

max(a[i], a[i+1]) / min(a[i], a[i+1]) <= 2

문제는 주어진 배열을 밀집하게 만들기 위해 추가해야 할 숫자의 최소 개수를 구하여야 한다.

두 인접한 숫자가 밀집하지 않을 경우, 작은 값으로 큰 값을 나눈 몫이 2 이하가 될 때 까지 2로 나누는 횟수가 추가해야할 숫자의 최소 개수가 된다.