[백준 19648번 문제] 미하일 2마리

 

문제 설명

위의 그림처럼 된 방향 그래프가 있다. 여기서 미하일이란 캐릭터가 파란색 지점에 총 2마리 놓여있다.1초마다 각 미하일은 인접 노드로 움직인다. 하지만 두 미하일은 각각의 위치에서 반대 미하일까지의 거리가 3이하가 되는 경로쌍으로는 이동하지 않게 되어있다.
이런 조건으로 N초가 흘렀을 때 미하일들이 사냥할 수 있는 경로의 총 방법 수를 구해라. 단 두 미하일이 a, b에 있는 경우와 b, a에 있는 경우는 다른 경우로 취급한다.

입력

10억 이하의 정수

출력

n초 동안 사냥할 수 있는 총 방법 수를 1,000,000,007로 나눈 나머지

과정

입력값의 시간초가 10억이다. 얼핏보면 시간제한이 7초이기 때문에 풀 수 있을 것처럼 느껴지기도 하지만 사실 10억 초에 순간마다 100번만 계산을 해도 총 계산은 1000억이다.

이렇게 절대 선형 시간안에 풀 수 없는 문제들은 반드시 log 시간안에 풀 수 있는 방법이 있을 것이라고 봐도 무방하다. logN을 사용하는 DP라고 생각해보니 LCA(최소 공통조상 문제) 가 생각이났다. 그리고 이 LCA 알고리즘은 문제에 딱 알맞게 적용될 수 있다.

1. 주어진 n초를 이진수로 분해한다.
2. n초가 11(2) 같은 정수였을 경우 n초뒤의 총 경우의 수는 = Σ(시작지점에서 1초뒤 움직일 수 있는 경우들 중 하나) * (움직일 수 있는 경로에서 2초 뒤에 가있을 수 있는 경로들) 이라고 말할 수 있고 재귀적으로 더 높은 숫자에 대해서도 적용될 수 있다.
3. 존재할 수 있는 위치에 대한 경우의 수는 14 * 13 이하이기 때문에 경우의 수가 많지 않다.

이렇게 LCA를 짰다면 점화식과, 자료구조를 짜야한다.

다음과 같은 제약조건이 있다.

1. 자료구조는 지금의 위치, log 시간대는 반드시 가지고 있어야한다.
2. 특정 위치에서 시간 n초 만큼 지났을 때의 이동할 수 있는 총 개수만이 아니라 n초만큼 지났을 때 또 196개의 각각의 위치로 이동할 수 있는 경우의 수가 필요하다.

자료구조를 정할 때는 그 자료구조가 저장해놓는 정보가 무엇인지를 설명할 수 있는 능력이 반드시 필요하다고 생각한다. 제약조건에 따르면 특정 시점에서 특정 시간에 다른 특정 위치로 이동할 수 있는 경우의 수가 몇 개인지를 필요로 한다는 것을 알 수 있다. 그래서 자료구조는

시작점, 특정 시간의 로그값, 그 시작점에서 특정 시간대에 이동한 특정 지점 3가지의 변수를 갖는 자료구조로 설정하려한다.

자료구조를 말로 설명하자면 dp[a][b][c] 는 현재의 내 위치 a에서 2의 b승만큼 시간이 흘렀을때 특정위치 c로 이동할 경우의 수라고 표현할 수 있다.

그리고는 점화식은 이렇게 설정했다.
현재 {내 위치 a에서 b초 뒤에 c로 이동할 수 있는 경우의 수}는 Σ {a에서 b/2초 뒤에 특점 지점으로 이동할 수 있는 경우의수} * {그 특정 지점에서 c로 이동할 수 있는 경우의 수} 이다.

알고리즘 개요도

초기 설정과 0번 인덱스를 채우는 코드

 

 

DP 값을 채우는 코드

 

입력값 N초에 대한 모든 정답 경우의 수를 찾는 코드

 

보다시피 말도 안되게 코드가 길고 복잡하다. 이걸 행렬로 해결하는 코드도 있다는데 조사해봐야겠다.

알고리즘

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
const int MAXNUM = 1000000007;

vector<vector<int>> lines(14, vector<int>{});
long long dp[196][32][197] = {0};
int distances[14][14] = {0};

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    lines[0] = {5};
    lines[1] = {0, 5, 10};
    lines[2] = {1};
    lines[3] = {2};
    lines[4] = {3};
    lines[5] = {0, 9};
    lines[6] = {1, 3, 7, 11, 12};
    lines[7] = {3, 8};
    lines[8] = {3, 4};
    lines[9] = {10};
    lines[10] = {6, 11};
    lines[11] = {12};
    lines[12] = {7, 13};
    lines[13] = {8};

    int seconds;
    cin >> seconds;
    
    int logSize = 1;
    int logDigit = 2;
    while (logDigit <= seconds)
    {
        logSize++;
        logDigit *= 2;
    }
    
    for (int i = 0; i < 14; i++)
    {
        int visited[14] = {0};
        visited[i] = 1;
        queue<int> A;
        queue<int> B;
        A.push(i);
        int level = 1;
        while (!A.empty())
        {
            // cout << A.front() << '\n';
            int num = A.front();
            A.pop();
            for (int next : lines[num])
            {
                if (visited[next] == 0)
                {
                    distances[i][next] = level;
                    visited[next] = 1;
                    B.push(next);
                }
            }
            if (A.empty())
            {
                while (!B.empty())
                {
                    A.push(B.front());
                    B.pop();
                }
                level++;
            }
        }
    }
    for (int i = 0; i < 14; i++)
    {
        for (int j = 0; j < 14; j++)
        {
            if (distances[i][j] < 3 || distances[j][i] < 3)
            {
                continue;
            }
            else
            {
                for (int ii : lines[i])
                {
                    for (int jj : lines[j])
                    {
                        if (distances[ii][jj] < 3 || distances[jj][ii] < 3)
                        {
                            continue;
                        }
                        dp[i * 14 + j][0][ii * 14 + jj] = 1;
                    }
                }
            }
        }
    }
    // 4초 뒤라면 2초뒤의 모든 애들에 대해서
    // 현재 가 13, 13의 1초라면
    // 1ㅗㅊ뒤에 거기 갔다는건데 그럼 그 간놈의 1초뒤를 따라서 2초뒤로 더해줌
    for (int time = 1; time < logSize; time++)
    {
        for (int i = 0; i < 14; i++)
        {
            for (int j = 0; j < 14; j++)
            {
                // 다음
                for (int ii = 0; ii < 14; ii++)
                {
                    for (int jj = 0; jj < 14; jj++)
                    {
                        if (distances[ii][jj] < 3 || distances[jj][ii] < 3)
                        {
                            continue;
                        }
                        for (int kk = 0; kk < 14; kk++)
                        {
                            for (int pp = 0; pp < 14; pp++)
                            {
                                if (distances[kk][pp] < 3 || distances[pp][kk] < 3)
                                {
                                    continue;
                                }
                                long long val = dp[i * 14 + j][time - 1][ii * 14 + jj] * dp[ii * 14 + jj][time - 1][kk * 14 + pp];
                                long long nextThing = val % MAXNUM;
                                dp[i * 14 + j][time][kk * 14 + pp] += nextThing;
                                dp[i * 14 + j][time][kk * 14 + pp] %= MAXNUM;
                            }
                        }
                    }
                }
            }
        }
    }
    long long answers[196] = {0};
    answers[21] = 1;
    int binary = 1;
    for (int fromLow = 0; fromLow < logSize; fromLow++)
    {
        long long tmp[196] = {0};
        if (binary & seconds)
        {
            for (int o = 0; o < 196; o++)
            {
                for (int d = 0; d < 196; d++)
                {
                    tmp[d] += answers[o] * dp[o][fromLow][d];
                    tmp[d] %= MAXNUM;
                }
            }

            for (int i = 0; i < 196; i++)
            {
                answers[i] = tmp[i];
            }
        }

        binary <<= 1;
    }

    long long ans = 0;
    for (int asdf = 0; asdf < 196; asdf++)
    {
        ans += answers[asdf];
        ans %= MAXNUM;
    }
    cout << ans;

}

 

결과