[BAE/<JOON> 문제풀이] 12931. 두배 더하기

https://www.acmicpc.net/problem/12931

12931번: 두 배 더하기

 

서론

그리디 문제

---

풀이

각 자리마다 1씩 더하면 경우의 수가 너무 많아진다.

0 배열에서 시작하는게 아닌 입력 배열에서 거꾸로 2씩 나눠가며 각 자리마다 나오는 나머지의 합을 거리 비용으로 계산하여 TLE를 피할 수 있다. 2로 나누는 비용과 1을 빼는 비용은 같으므로 항상 이 경우가 최적일 수 밖에 없다.

최적이 아니려면 2로 나누는 비용이 따로 주어져 2로 나누는 것 보다 1씩 연산하는게 더 적은 비용인 경우가 있어야 한다. 이 문제는 그런게 없으니까 이렇게 탐욕적으로 최적화를 할 수 있다.

---

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;
int mvx[6] = { 0, 1, 1, -1, -1, 0 };
int mvy[6] = { 1, 1, 0, 0, -1, -1 };
struct node {
    vector<int> arr;
    int cnt = 0;
};
struct cmp {
    bool operator() (node a, node b) {
       return a.cnt > b.cnt;
    }
};
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n; vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    priority_queue<node, vector<node>, cmp> q;
    q.push({ arr, 0 });
    while (!q.empty()) {
        auto cur = q.top(); q.pop();
        if (cur.arr.size() == 0) {
            cout << cur.cnt;
            return 0;
        }
        
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += cur.arr[i];
        }
        q.push({ {}, cur.cnt + sum });

        auto cp = cur.arr;
        sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += cp[i] % 2;
            cp[i] /= 2;
        }
        q.push({ cp, cur.cnt + sum + 1 });
    }
    return 0;
}