글 읽기 - 제 소스의 문제점을 모르겠습니다...ㅠ(수정)

lsh9034 5년 전 0

저번에 질문했던 코드에서는 문제점을 찾았습니다. 그래서 그 문제점을 해결한 새로운 소스를 짰는데요 그래도 틀리더라구요. 이제는 정말 뭐가 문제인지 모르겠네요... dp[51][51][51][51]배열을 썼구요. [행][열][거처간 오락실 갯수][마지막으로 방문한 오락실 번호] = 경로의 갯수로 했습니다.

현재 위치가 오락실이 아니면 C까지 오락실이라면 전에 나보다 큰 오락실 번호를 가진 오락실은 내 위치에 올 수 없으므로 현재 오락실 번호까지만 for문을 돌렸습니다.

그리고 입력받을 때 오락실의 위치가 (x,y)이므로 [y][x]=오락실번호로 처음에 인풋배열을 설정해주었습니다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int M = 1000007;
int n, m, c;
int map[51][51];

int dp[51][51][51][51];
void sol(int i, int j)
{
	if (map[i][j] == 0)
	{
		for (int k = 0; k <= c; k++)
		{
			for (int r = 0; r <= c; r++)
			{
				dp[i][j][k][r] = (dp[i][j][k][r] + dp[i - 1][j][k][r]+ dp[i][j - 1][k][r]) % M;
			}
		}
	}
	else
	{
		for (int k = 0; k < map[i][j]; k++)
		{
			for (int r = 0; r < map[i][j]; r++)
			{
				if (dp[i - 1][j][k][r] != 0)
				{
					int R = map[i][j];
					dp[i][j][k + 1][R] = (dp[i][j][k + 1][R] + dp[i - 1][j][k][r]) % M;
				}

				if (dp[i][j - 1][k][r] != 0)
				{
					int R = map[i][j];
					dp[i][j][k + 1][R] = (dp[i][j][k + 1][R] + dp[i][j - 1][k][r]) % M;
				}
			}
		}
	}
}
int main(void)
{
	cin >> n >> m >> c;
	for (int i = 1; i <= c; i++)
	{
		int x, y;
		cin >> x >> y;
		map[y][x] = i;
	}
	if (map[1][1])
	{
		dp[1][1][1][map[1][1]] = 1;
	}
	else
	{
		dp[1][1][0][0]= 1;
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			sol(i, j);

	for (int k = 0; k <= c; k++)
	{
		int answer = 0;
		for (int r = 0; r <= c; r++)
		{
			answer =(answer + dp[n][m][k][r])%M;
		}
		cout << answer << ' ';
	}
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제 소스의 문제점을 모르겠습니다...ㅠ(수정)

lsh9034 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말