백준 - 1513번 : 경로 찾기 (C++)

풀이 방법 : DP

DP로 풀어야겠다는 건 빨리 캐치했지만 DP 테이블을 [r][c][오락실 갯수]의 3차원 배열로만 생각해서 아무리 풀어도 못풀겠더라 그래서 검색을 해보니 4차원 배열을 사용해야 하는 문제라고 한다...

그 말을 보고 생각해보니 단순히 오락실 번호뿐만 아니라 지금까지 들른 오락실의 갯수와 그 중 가장 최대의 번호까지 고려를 해줘야 하는구나 싶더라 예를 들어서 3번 오락실을 처음으로 들르는 케이스와 2번째로 들르는 케이스, 다른 곳 다 들르고 세번째로 들르는 케이스들을 다 따로 처리해줘야하니까..

모든 문제가 그렇듯 알고보면 당연한 얘기다...

#include <iostream>

using namespace std;

int N, M, C;
int Map[51][51] = {};
int DP[51][51][51][51] = {}; //r, c, 오락실 최대번호, 들른 오락실 갯수

int main()
{
	cin >> N >> M >> C;

	for (int i = 1; i <= C; ++i)
	{
		int X, Y;
		cin >> X >> Y;

		Map[X][Y] = i;
	}

	if (Map[1][1] == 0)
		DP[1][1][0][0] = 1;

	else
		DP[1][1][Map[1][1]][1] = 1;

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= M; ++j)
		{
			if (i == 1 && j == 1)
				continue;

			int Flag = Map[i][j];

			if (Flag == 0) //오락실이 아닌 경우
			{
				for (int k = 0; k <= C; ++k)
				{
					for (int x = 0; x <= C; ++x)
					{
						DP[i][j][x][k] += DP[i - 1][j][x][k] % 1000007;
						DP[i][j][x][k] += DP[i][j - 1][x][k] % 1000007;
					}
				}
			}

			else //오락실인 경우
			{
				for (int k = 1; k <= C; ++k)
				{
					for (int x = 0; x < Flag; ++x)
					{
						DP[i][j][Flag][k] += DP[i - 1][j][x][k - 1] % 1000007;
						DP[i][j][Flag][k] += DP[i][j - 1][x][k - 1] % 1000007;
					}
				}
			}
			
		}
	}

	for (int i = 0; i <= C; ++i)
	{
		int Cnt = 0;

		for (int j = 0; j <= C; ++j)
		{
			Cnt += DP[N][M][j][i] % 1000007;
		}

		Cnt %= 1000007;

		cout << Cnt << ' ';
	}
}

눈물난다... 3시간 고민해도 못풀었는데... 4차원 배열 써야한다는 사실을 알고나니 10분만에 풀리는걸..
이 문제는 두고두고 곱씹어야겠다.