BOJ 15942 Thinking Heap

Thinking Heap
(http://boj.kr/15942)

방법은 여러가지가 있을 것 같다.
나는 이동이 전혀 일어나지 않도록 만들었다.
그 노드에 수를 넣었다면, 부모들은 자신보다 작아야하고, 자식들 중에 자신보다 작은건 없어야 한다.

어떻게 넣을지는 상관없다. 나는 자신보다 작아야 하는 수는 1부터 넣었고, 커야 하는 수는 n부터 넣었다. 그리고 상관없는건 남는 수들을 아무렇게나 넣었다.

불가능한 경우는 당연하게도, 작아야 하는 수의 개수가 자신보다 작은 수보다 많을 때와 커야하는 수의 개수가 자신보다 큰 수보다 많을 때이다. 그 외의 경우는 모두 가능하다.

 

 

#include <bits/stdc++.h>
 
int n, cnt1, cnt2, cnt3, chk[200001];
 
void f(int now) {
    if (now > n)
        return;
 
    cnt2++;
    chk[now] = -1;
 
    f(now * 2);
    f(now * 2 + 1);
}
 
int main() {
    int m, k, t;
 
    scanf("%d %d %d", &n, &m, &k);
 
    t = k / 2;
    while (t >= 1) {
        cnt1++;
        chk[t] = 1;
        t /= 2;
    }
 
    f(k * 2);
    f(k * 2 + 1);
 
    if (cnt1 >= m || cnt2 > n - m) {
        printf("-1");
 
        return 0;
    }
 
    cnt3 = cnt1 + 1;
    cnt1 = 1;
    cnt2 = n;
    for (int i = 1;i <= n;++i) {
        if (i == k) 
            printf("%d\n", m);
        else if (chk[i] == 1)
            printf("%d\n", cnt1++);
        else if (chk[i] == 0) {
            if (cnt3 == m)
                cnt3++;
            printf("%d\n", cnt3++);
        }
        else
            printf("%d\n", cnt2--);
    }
 
    return 0;
}