문제 설명
랩실 구석에서 불장난을 하다가 불이 났습니다!
랩실이 문제와 같이 주어졌을 때 두 사람이 부딪히지 않고 안전하게 방을 빠져나오는 경우의 수를 구하세요!
풀이
두 사람이 이동할 수 있는 경우는 이렇게 4가지가 있습니다.
이 4가지 이동을 하면서 모든 경우를 계산하려고 합니다.
완전 탐색을 하여 4가지 이동을 할 때 안전하게 문에 도착했을 때 경우의 수를 세어주게 되면
시간 복잡도가 O(4^N)이 되어 시간이 많이 걸리게 됩니다.
그럼 어떻게 해야 할까요??
모든 경우를 보다 보면 두 사람의 위치가 전과 동일할 때가 있습니다.
전에 그 두 사람이 그 위치에 있었을 때 경우의 수를 구했었기 때문에
또 둘이 그 위치에 서 있다면 경우의 수를 또 구하러 탐색하지 않고 전에 구했던 경우의 수를 쓰면 됩니다.
즉, 중복되는 문제가 있기 때문에 DP로 접근을 해야 합니다.
4가지 이동에서 3가지는 둘이 어느 위치에 있던 부딪히지 않지만 4번째 이동은 둘의 거리에 따라 부딪힐 수 있습니다.
그러므로 저는 이 4번째 이동을 고려해 주기 위해 이런 식으로 DP 배열을 구성하였습니다.
DP[타일 수][두 사람의 거리] = 조건에서 안전하게 빠져나가는 경우의 수
이렇게 DP를 구성하여 4번째 이동을 처리할 수 있습니다.
현재 타일 수 - now, 두 사람의 거리 - dist
DP[now][dist] = DP[now - 1][dist] * 2 + DP[now - 1][dist - 1] + DP[now - 1][dist + 1]
로 점화식을 완성할 수 있습니다.
DP[5][2]를 구해보겠습니다.
위 그림에서 1,3번째 이동은 이동 시에 두 사람의 거리가 변하지 않습니다.
그래서 DP[5][2]에 DP[4][2] * 2를 더하면 됩니다.
2번째 이동은 두 사람의 거리가 1이 증가하기 때문에 DP[5][2]에 DP[4][1]를 더하면 됩니다.
4번째 이동은 두 사람의 거리가 1이 감소하기 때문에 DP[5][2]에 DP[4][3]을 더하면 됩니다.
이렇게 하여 두 사람의 거리가 1일 때 4번째 이동 값을 더해주지 않으면 됩니다.
그리고 DP[N][1] ~ DP[N][N - 1]을 더하면 안전하게 빠져나갈 수 있는 경우의 수를 구할 수 있습니다!!
모듈러 연산 꼭 해주세요 ㅎㅎ
소스 코드
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int main() {
FIO;
int n, sum = 0, dp[105][105] = {};
cin >> n;
dp[2][1] = 2;
FOR(i, 3, n) FOR(j, 1, i - 1)
dp[i][j] = (dp[i - 1][j] * 2 + dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 10007;
FOR(i, 1, n - 1) sum += dp[n][i];
cout << sum % 10007 << '\n';
return 0;
}