BOJ 15942 : Thinking Heap

• 문제 링크 : boj.kr/15942
• 난이도 : G2
• 태그 : 그리디, 해 구성하기

---

코드

#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>;

bool parent(int a, int b) {
    while(b != 0 && a < b) b /= 2;
    return a == b;
}

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

    int n;
    cin >> n;
    int k, p;
    cin >> k >> p;

    vector<int> ans(n+1);
    int l = 1, r = k+1;
    for(int i = 1; i <= n; i++) {
        if(i < p && parent(i, p)) {
            if(l == k) {
                cout << -1;
                return 0;
            }
            ans[i] = l++;
        }
        if(i == p) ans[i] = k;
        if(p < i && parent(p, i)) {
            if(r == n+1) {
                cout << -1;
                return 0;
            }
            ans[i] = r++;
        }
    }
    for(int i = 1; i <= n; i++) {
        if(ans[i] == 0) {
            if(l < k)ans[i] = l++;
            else ans[i] = r++;
        }
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << "\n";

    return 0;
}

---

풀이

p의 부모에는 k보다 작은 값을, 자식에는 k보다 큰 값을 놓는다. 빈 곳에는 아직 놓지 않은 자연수를 놓아주면 된다.