[BAE/<JOON> 문제풀이] 1513. 경로 찾기

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

1513번: 경로 찾기

1513:: 경로 찾기

핵심::
기본 DP 문제
고려해야할 요소들이 많기는 하지만 기본 DP 문제 틀에서 벗어나지는 않음

풀이::
DP[x 위치][y 위치][방문한 오락실 중 최대 번호][방문한 오락실 갯수] = 위 조건을 만족하는 경로 갯수

점화식은 다음과 같음

현재 칸이 오락실일 경우::

현재 칸으로 올 수 있는 윗칸과 아랫칸에서 방문한 오락실 번호가 현재 오락실 번호보다 작은 모든 오락실 경로의 합을 구한다.

for(l = 0 ~ 현재칸 오락실 번호 - 1)
for(k = 1 ~ l)
DP[x][y][현재칸 오락실 번호][k] = sum(dp[x - 1][y][l][k - 1] + dp[x][y - 1][l][k - 1])


현재 칸이 오락실이 아닌 경우::

별도의 계산없이 경로 수를 횡전개만 해주면 된다.

for(l=0 ~ 오락실 개수) 
for(k = 0 ~ l) 
DP[x][y][l][k] = DP[x - 1][y][l][k] + DP[x][y - 1][l][k];

의견::
점화식 틀린 줄 알고 거진 4시간 고민했는데 모듈러 연산 코드를 마지막 합산하는 부분에 작성을 안했다.

코드::

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int cc = 1000007;

int dp[51][51][51][51]; //[][]위치[번호 최댓값][통과한 오락실 갯수] = 경로 갯수

int main()
{
	int n, m, c;
	cin >> n >> m >> c;
	vector<vector<int>> arr(n + 1, vector<int>(m + 1));

	dp[1][1][0][0] = 1;
	for (int i = 1; i <= c; i++) {
		int x, y;
		cin >> x >> y;
		if (x == 1 && y == 1) {
			dp[1][1][0][0] = 0;
			dp[1][1][i][1] = 1;
		}
		arr[x][y] = i;
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (i == 1 && j == 1) continue;
			if (arr[i][j] > 0) {
				for (int l = 0; l < arr[i][j]; l++) {//l = 방문한 최대 오락실 번호 ( 0 은 오락실은 아니지만 오락실을 한번도 방문하지 않은 경우 모든 오락실 출입 가능 )
					for (int k = 0; k <= l; k++) {// k = 방문 갯수 
						dp[i][j][arr[i][j]][k + 1] += dp[i - 1][j][l][k] + dp[i][j - 1][l][k]; // 현재 오락실 번호 이하의 경로 수 총합
						dp[i][j][arr[i][j]][k + 1] %= cc;
					}
				}
			}
			else { 
				//오락실이 아닌 경우에는 갈 수 있는 경로 수 횡전개
				for (int l = 0; l <= c; l++) {
					for (int k = 0; k <= l; k++) {
						dp[i][j][l][k] = dp[i  - 1][j][l][k] + dp[i][j - 1][l][k];
						dp[i][j][l][k] %= cc;
					}
				}
			}
		}
	}	

	for (int i = 0; i <= c; i++) {
		int sum = 0;
		for (int j = 0; j <= c; j++) {
			sum += dp[n][m][j][i];// 방문 갯수 별 경로 수 합계
		}
		sum %= cc;
		cout << sum << " ";
	}

	return 0;
}