[백준] 12849번 : 본대 산책

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 1 ~ n분까지 모든 시간에 각 건물에 도착하는 경우의 수를 2차원 배열 dp에 갱신하는 Bottom-Up 방식으로 풀었다.

각 건물의 번호는 다음과 같이 지정한다.

• 정보과학관 : 0 / 전산관 : 1 / 미래관 : 2 / 신양관 : 3 / 한경직기념관 : 4 / 진리관 : 5 / 학생회관 : 6 / 형남공학관 : 7

1) 산책 시간을 입력 받아 n에 저장한다.

2) 2차원의 dp 배열을 선언하고, dp[0][0]을 1로 초기화한다.

• dp[i][j] : i번 건물에 j분에 도착하는 경우의 수
• 0번 건물인 정보과학관에 0분에 도착하는 경우의 수는 그 자리에서 움직이지 않는 것 한 가지의 경우밖에 없기 때문에 1이다.

3) 1분부터 n분까지 각 건물에 도착하는 경우의 수를 갱신한다.

• n분에 어떤 건물에 도착하기 위해서는 n-1분에 해당 건물과 인접한 건물에 도착해야 한다.
• 만약 3분에 1번 건물인 전산관에 도착하는 경우의 수를 알고 싶다면
  • 2분에 정보과학관에 도착할 경우 + 2분에 미래관에 도착할 경우 + 2분에 신앙관에 도착할 경우를 전부 더한 값이 될 것이다.
  • 위 과정을 식으로 표현하면 dp[1][3] = dp[0][2] + dp[2][2] + dp[3][2]
• 따라서 위와 같은 과정을 모든 건물에 대해 모든 시간에 적용하면 dp가 갱신된다.

4) 최종적으로 n분에 정보과학관에 도착하는 경우를 알고 싶은 것이므로 dp[0][n]를 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long dp[8][100001];			// dp[i][j] : i번 건물에 j분에 도착하는 경우의 수
const long long MOD = 1000000007;
int n;

// 정보과학관 : 0 / 전산관 : 1 / 미래관 : 2 / 신양관 : 3 / 한경직기념관 : 4 / 진리관 : 5 / 학생회관 : 6 / 형남공학관 : 7
long long solution()
{
	dp[0][0] = 1;

	// i번 건물에 j분에 도착하는 경우의 수는 (i번 건물에 연결된 건물들에 i-1분에 도착하는 경우의 수의 합)
	for (int i = 1; i <= n; i++)
	{
		dp[0][i] = (dp[1][i - 1] + dp[2][i - 1]) % MOD;
		dp[1][i] = (dp[0][i - 1] + dp[2][i - 1] + dp[3][i - 1]) % MOD;
		dp[2][i] = (dp[0][i - 1] + dp[1][i - 1] + dp[3][i - 1] + dp[4][i - 1]) % MOD;
		dp[3][i] = (dp[1][i - 1] + dp[2][i - 1] + dp[4][i - 1] + dp[5][i - 1]) % MOD;
		dp[4][i] = (dp[2][i - 1] + dp[3][i - 1] + dp[5][i - 1] + dp[7][i - 1]) % MOD;
		dp[5][i] = (dp[3][i - 1] + dp[4][i - 1] + dp[6][i - 1]) % MOD;
		dp[6][i] = (dp[5][i - 1] + dp[7][i - 1]) % MOD;
		dp[7][i] = (dp[4][i - 1] + dp[6][i - 1]) % MOD;
	}
	return dp[0][n];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n;
	cout << solution();
}