BOJ 12931 : 두 배 더하기

• 문제 링크 : boj.kr/12931
• 난이도 : G5
• 태그 : 그리디

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<int> arr(n);
    for(auto &u : arr) cin >> u;

    int ans = 0;
    int L = 0;
    for(auto u : arr) {
        int l = 0;
        while(u) {
            ans += u % 2;
            u /= 2;
            l++;
        }
        L = max(L, l);
    }
    cout << max(0, ans + L - 1);

    return 0;
}

---

풀이

{1, 4, 8, 9, 11}이라는 배열의 값을 2진수로 나타내보자.

1 = 1(2), 4 = 100(2), 8 = 1000(2), 9 = 1001(2), 11 = 1011(2)이다.

자릿수가 가장 긴 수에 자릿수를 맞춰보면 순서대로 0001, 0100, 1000, 1001, 1011이다.

앞에서부터 배열의 값을 차례대로 맞춰주고, 곱하기 연산을 시행할 것이다.

 

예를 들어보자.

처음 상태에서 배열을 {0, 0, 1, 1, 1}로 맞춘다.

곱하기 연산을 시행하여 배열을 {00, 00, 10, 10, 10}으로 만든다.

다시 배열을 {00, 01, 10, 10, 10}으로 맞춘다.

곱하기 연산을 시행하여 배열을 {000, 010, 100, 100, 100}으로 만든다.

다시 배열을 {000, 010, 100, 100, 101}으로 맞춘다.

곱하기 연산을 시행하여 배열을 {0000, 0100, 1000, 1000, 1010}으로 만든다.

최종적으로 배열을 {0001, 0100, 1000, 1001, 1011}으로 맞추면 끝이다.

 

따라서 우리는 답이 "가장 긴 자릿수 + 원소들에 있는 1의 수 - 1"이 됨을 알 수 있다.