[C/C++] 백준 - 12849번 : 본대 산책

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

12849번: 본대 산책

문제

숭실 대학교 정보 과학관은  캠퍼스의 길 건너편으로 유배를 당했다. 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다. 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 본대를 가고 싶어 한다. 어느 날 준영이는 본대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다.

(편의 상 문제에서는 위 건물만 등장한다고 가정하자)

한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를 구해주자.

입력

D 가 주어진다 (1 ≤ D ≤ 100,000) 

출력

가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력 한다.

---

가능한 경로의 경우의 수를 구하는 문제이다. 우선 이 문제는 문제 해결에 앞서 주어진 지도를 그려주어야한다. 나는 정보문화관을 1번 노드로 가정하고 나머지는 순서대로 2,3,4,5,6,7,8 노드라고 정하고 진행하였다. 그려주는 건 벡터에 양방향 관계를 넣어 길이 있음을 나타내주었다.

 

길은 대부분 중복되는 부분이 존재한다. 따라서 완전탐색으로 모든 경우의 수를 확인하려하면 무조건 시간초과가 난다. 

중복된 길의 방문을 방지하여 중복을 제거해주어야 시간 내 통과가 가능하다. 즉, 동적계획법을 적용하여 문제를 해결해야한다.

 

나는 메모이제이션을 cache[남은 시간][노드 번호]로 적용하였다.

어떤 한 노드를 방문했을 때 남은 시간을 메모이제이션하여 같은 시간일 때 같은 노드를 방문하는 중복을 제거해주었다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define Mod 1000000007
#define endl '\n'

using namespace std;

int t;
long long cache[100000 + 1][10];
vector<int> adj[10];

void init(){
    // 정보과학관을 1번으로 지정
    adj[1].push_back(2);
    adj[2].push_back(1);

    adj[1].push_back(3);
    adj[3].push_back(1);

    adj[2].push_back(3);
    adj[3].push_back(2);

    adj[2].push_back(4);
    adj[4].push_back(2);

    adj[3].push_back(4);
    adj[4].push_back(3);

    adj[3].push_back(5);
    adj[5].push_back(3);

    adj[4].push_back(5);
    adj[5].push_back(4);

    adj[4].push_back(6);
    adj[6].push_back(4);

    adj[5].push_back(6);
    adj[6].push_back(5);

    adj[6].push_back(7);
    adj[7].push_back(6);

    adj[5].push_back(8);
    adj[8].push_back(5);

    adj[7].push_back(8);
    adj[8].push_back(7);
}

void input(){
    cin >> t;
}

long long path(int restTime, int node){
    if(restTime == 0){
        if(node == 1) return 1;
        else return 0;
    }
    long long &ret = cache[restTime][node];
    if(ret != -1) return ret;

    ret = 0;
    for(auto &y : adj[node]){
        ret += path(restTime-1, y) % Mod;
    }
    return ret % Mod;
}

long long solution(){
    long long count = 0;
    memset(cache, -1, sizeof(cache));
    for(auto &next : adj[1]){
        count += path(t-1, next) % Mod;
    }
    return count % Mod;
}

int main(){
    fastio;
    init();
    input();
    cout << solution() << endl;

    return 0;
}