[백준 12849번] 본대 산책 (C++)

문제링크 : https://www.acmicpc.net/problem/12849

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
long long dp[8], arr[8];
//정보, 전산, 신양, 진리, 학생, 형남, 환경, 미래

int main() {
    int D;
    cin >> D;

    dp[0] = 1; // 정보과학관에서 시작

    while (D--) {
        arr[0] = dp[1] + dp[7];           // 정보 - 전산, 미래
        arr[1] = dp[0] + dp[2] + dp[7];   // 전산 - 정보, 신양, 미래
        arr[2] = dp[1] + dp[3] + dp[6] + dp[7];  // 신양- 전산, 진리, 환경, 미래
        arr[3] = dp[2] + dp[4] + dp[6];  // 진리 - 신양, 학생, 환경
        arr[4] = dp[3] + dp[5];  // 학생 - 진리, 형남
        arr[5] = dp[4] + dp[6];  // 형남 - 학생, 환경
        arr[6] = dp[2] + dp[3] + dp[5] + dp[7];  // 환경 - 신양, 진리, 형남, 미래
        arr[7] = dp[0] + dp[1] + dp[2] + dp[6];  // 미래 - 정보, 전산, 신양, 환경

        for (int i = 0; i < 8; i++)
            dp[i] = arr[i] % MOD;
    }

    cout << dp[0] << "\n"; 
    return 0;
}

 

정해진 그래프의 인접한 건물을 통해 dp 식을 계산해준다.

본인의 경우 인덱스 0~7까지를 정보, 전산, 신양, 진리, 학생, 형남, 환경, 미래로 정하였다.

이에 맞춰서 전산을 예시로 들면 연결된 정보, 신양, 진리, 미래에 도달 가능한 경우의 수를 더해주면 된다.

D분이 지나 다시 정보과학관에 돌아오므로 D번 만큼 반복문을 돌려 갱신된 dp[0]을 출력해주면 된다.