[BOJ] 백준 28042 - City Folding

작성일 | In

문제 정보

    사용 알고리즘

    • 비트마스크(Bitmask)
    • 수학(Mathematics)

    문제

    처음에 아래 그림과 같이 $1$부터 $2^N$까지의 수가 일렬로 적혀있는 종이 조각이 있습니다. 이 종이 조각을 왼쪽 혹은 오른쪽 절반을 위로 접는 것을 $N$번 반복해 각 층마다 $1$개의 종이 조각씩 총 $2^N$층으로 만들었습니다.(매번 왼쪽, 오른쪽을 정할 수 있습니다) 이때, 처음에 $P$번이 아래서부터 $H$번째가 되도록 접는 방법을 찾아 출력하는 문제입니다. 아래 그림은 $2^3$개에서 $4$번이 $7$층이 되도록 LRL로 접는 방법을 나타냅니다.

    문제 제한

    • $3 \leq N \leq 60$
    • $1 \leq P, H \leq 2^N$
    • 답이 유일하게 존재함이 보장됩니다.(증명 가능합니다)

    풀이

    예제의 상황인 $N=3$, $P=4$, $H=7$을 생각해 봅시다. 또, $1$부터 $2^N$까지를 비트마스킹을 위해 $0$부터 $2^N-1$로 생각하겠습니다. 그리고 아래와 그림과 같이 빨간 글씨대로 자리의 번호를 정합니다. 이제 최종 마지막 상태에서 역으로 생각해 보면 다음을 알 수 있습니다.

    • 4번째에서 $6$번 자리였다면, 3번째에서는 $2$ 혹은 $3$번 자리입니다.
    • 3번째에서 $2$ 혹은 $3$번 자리였다면, 2번째에서는 $4$, $5$, $6$, $7$번 자리중 하나입니다.
    • 2번째에서 $4$, $5$, $6$, $7$번 자리였다면, 1번째에서는 모든 자리가 가능합니다.

    이 자리들을 보면 층수가 같습니다. 따라서 이를 층수에 따라 생각해보겠습니다. 마찬가지로 가장 아래를 $0$층이라 하겠습니다. 층수는 위에 파란 글씨로 표시해두었습니다.

    • 4번째에서 $6(110_2)$층이였다면, 3번째에서는 $1(01_2)$층입니다.
    • 3번째에서 $1(01_2)$층이였다면, 2번째에서는 $1(1_2)$층입니다.
    • 2번째에서 $1(1_2)$층이였다면, 1번째에서는 $0(0_2)$층입니다.

    또한, $i$번째 단계에서 층수가 총 $2^{i-1}$개의 층이 있는데, 이 중 절반($2^{i-2}$) 이상이라고 하면 접힌 쪽에서 접혔을 것이며, 이하라고 하면 위쪽이 접혀 올라왔습니다. 즉, 아래쪽이면 원래의 층수를 유지하며, 위쪽이면 원래 층수에서 절반에 해당하는 $2^{i-2}$을 빼준 후 비트를 뒤집어 주면 됩니다. 즉, 최상위 비트를 제거하고 비트를 flip합니다. 예를 들어 9번째의 높이가 이진수로 $11010010$의 경우 최상위 비트를 제거하면 $1010010$이 되고, 이를 flip하면 $0101101$이 8단계의 층이 됩니다. 9번째의 높이가 $01010010$일 경우 그 자리를 유지해(최상위 비트 $0$만 제거) $1010010$이 됩니다.

    이를 통해 각 단계에서의 층수를 모두 구할 수 있습니다. 이제 다시 원래에서 접어야 하는데, 우선 현재 위치가 절반보다 왼쪽인지 오른쪽인지 구한 뒤, 만약 다음 단계의 높이가 절반 이상이라면 원하는 종이조각이 있던 곳을 위로 올려야 하므로 해당 방향을, 아니면 그대로 두어야 하므로 반대 방향을 출력하면 됩니다.

    구현

    비트 플립을 구현할까 하다가 어차피 $x$자리라면 2진수로 $2^x-1$에서 빼면 됨을 통해 그냥 빼서 구현했습니다. 시프트 할 때 1<<x와 같이 하면 오버플로우가 나니까 1LL<<x혹은 1ll<<x로 해야 합니다. 또한, 사용하는 많은 변수를 64비트 정수형으로 선언해야 합니다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

void solve() {
    ll i,j;
    ll n,p,h;
    cin>>n>>p>>h;
    p--,h--;
    vector<ll>arr(n);
    for(i=0;i<n;i++){
        j=(1LL<<(n-i-1));
        if(h&j){
            arr[i]=1LL<<i;
            h=(j<<1)-1-h;
        }
    }
    reverse(arr.begin(), arr.end());
    for(i=0;i<n;i++){
        j=(1LL<<(n-i-1));
        if((p&j)==arr[i]){
            cout<<'R';
            if(p&j) {
                p=(j<<1)-1-p;
            }
        }
        else{
            cout<<'L';
            if(p&j){
                p^=j;
            }
            else{
                p=(j-1-p);
            }
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    cin.tie(0)->sync_with_stdio(0);
#endif
    int t = 1;
    //cin >> t;
    while (t--) solve();
}