[Algorithm]Baekjoon 12849번 :: 본대 산책

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int d;
long long nowDP[8] = { 0 };
long long nextDP[8] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> d;
 
    nowDP[0] = 1;
 
    while (d--)
    {
        nextDP[0] = nowDP[1] + nowDP[2];
        nextDP[1] = nowDP[0] + nowDP[2] + nowDP[3];
        nextDP[2] = nowDP[0] + nowDP[1] + nowDP[3] + nowDP[4];
        nextDP[3] = nowDP[1] + nowDP[2] + nowDP[4] + nowDP[5];
        nextDP[4] = nowDP[2] + nowDP[3] + nowDP[5] + nowDP[6];
        nextDP[5] = nowDP[3] + nowDP[4] + nowDP[7];
        nextDP[6] = nowDP[4] + nowDP[7];
        nextDP[7] = nowDP[5] + nowDP[6];
 
        for (int i = 0; i < 8; i++)
        {
            nowDP[i] = nextDP[i] % 1000000007;
        }
    }
 
    cout << nowDP[0];
}

 

 

여기서 nextDP[n]은 1분 후 n번노드로 갈 수 있는 경우의 수를 의미한다.

nowDP[n]은 n번 노드로 갈 수 있는 경우의 수를 의미한다.

 

nextDP를 업데이트하는 방식을 먼저 보자면, 1분 후 특정노드로 가기위해선 특정노드에 인접한 노드들에 가는 경우의 수를 모두 더해주면 된다. 인접한노드들에서는 특정노드까지 1분만에 갈 수 있기 때문이다.

여기서 각 dp테이블이 1차원이라 헷갈릴 수 있는데, nextDP를 업데이트하는 nowDP는 이전차례의 값이다.

 

그래서 반복문 이전에 nowDP[0]에 1을 넣는데, 이것은 '0분에 0번노드에 도착하는 경우의 수'인 1을 넣은거라 볼수 있다.

0분에 0번노드에 도착하는 경우의 수가 왜 1이냐면 그냥 그자리에 있으면 되기 때문이다.

 

그리고 마지막에 nowDP를 nextDP로 업데이트해주는데, 다음 반복문때 써야하기 때문이다.

딱 이전차례에서의 값만 필요하기때문에 굳이 D만큼의 추가 배열을 선언할필요없이, 노드개수로만 DP테이블을 정의해서 문제를 풀 수 있는 것이다.