[BOJ] 30190 - 여우의 꿈

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

BOJ - 여우의 꿈

문제 유형: 수학, 그리디, 재귀

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 128MB

 

문제

여우 마을에는 3개의 기둥과 N개의 원판을 가진 하노이 탑의 원판들을 한 곳에 모으면 소원이 이루어진다는 전설이 있다.

하노이 탑의 원판들을 이동시키는 규칙은 다음과 같다.

• i번째 원판의 반지름은 i이다. (1 <= i <= N)
• 어떤 시점에라도 한 기둥 안의 원판은 반지름이 작을수록 위로 오도록 정렬되어 있어야 한다.
• 각 기둥의 제일 위에 있는 원판만 이동할 수 있다.
• 원판은 기둥의 맨 위로만 이동할 수 있다.
• 원판은 한 번에 한 개만 이동할 수 있다.

여우 마을에 사는 아기 여우는 어느 날 이 소문을 듣고 하노이 탑에 도전하기로 했다. 아기 여우는 모든 원판을 K번째 기둥에 모으는 데 성공했고, 소원을 빌었다.

"세상에서 가장 귀여운 여우가 되게 해주세요!"

하지만 아기 여우에게는 아무런 변화도 일어나지 않았다.

실망한 아기 여우는 이번에는 자신이 생각하기에 아름다운 모양으로 원판을 배치해 보기로 했다. 이제는 하노이 탑의 고수가 된 아기 여우는 1초에 한 개의 원판을 옮길 수 있다. 아기 여우가 원판을 아름다운 모양으로 배치하는 데 걸리는 최소 시간을 구해 보자!

 

입력

첫 번째 줄에 N과 K가 공백을 사이에 두고 입력된다. (1 <= N <= 1,000,000; 1 <= K <= 3)

두 번째 줄에 N개의 수가 공백을 사이에 두고 입력된다. i번째 수 a_i는 i번째 원판이 아름다운 모양에서 몇 번째 기둥에 있는지 의미한다. (1 <= a_i <= 3)

아기 여우가 생각한 아름다운 모양은 하노이 탑의 규칙을 만족한다.

 

출력

첫 번째 줄에 아기 여우가 아름다운 모양을 만드는 데 걸리는 최소 시간(초)을 10^{9} + 7로 나눈 나머지를 출력한다. 10^{9} + 7은 소수이다.

아름다운 모양을 만드는 것이 불가능하면 -1을 출력한다.

 

풀이

사실 불가능한 경우는 없다. 맨 아래의 원판부터 우선으로 세워주기 위해, 다른 원판들이 비키면 되기 때문이다.

즉, 맨 아래 원판부터 배치해줄 것이다.

 

하노이 탑을 움직이기 위해, n층짜리를 옮기려고 하면, 2^n - 1회가 필요하다.

점화식으로 보면, f(n-1) * 2 + 1회 필요하다. f(1) = 1, f(0) = 0.

즉, 이 모든 층에 대해 프리컴퓨트 해준다.

 

맨 아래 원판을 배치하기 위해, 두 가지 경우의 수가 있다:

1. 맨 아래 원판이 이미 원하는 자리에 있는 경우 -> 움직일 필요 없다.

2. 맨 아래 원판을 옮겨야 하는 경우 -> f(i) + 1회 움직임 누적하기, 이후 남은 탑들의 위치는 6 - 목표지점 - 현재지점.

 

 

코드

C++

#include <bits/stdc++.h>
#define MAX 1000001

using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;

ll f[MAX];

void init() {
    f[0] = 0;
    for (int i = 1; i < MAX; i++) {
        f[i] = (f[i - 1] * 2 + 1) % MOD;
    }
}

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    init();

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

    vector<int> a(n);
    for (auto& i : a) cin >> i;

    vector<int> state(3);
    state[k - 1] = n;

    ll ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        int src = k;
        int dst = a[i];
        if (src == dst) {
            continue;
        }

        ans = (ans + f[i] + 1) % MOD;
        k = 6 - src - dst;
    }

    cout << ans << "\n";

    return 0;
}