글 읽기 - 반례를 못찾겠습니다...

leekh2002 4년 전 0

dp[y][x][k] -> y행 x열에서 시작하여 목표지점까지 k개의 오락실을 거쳐가는 경우의 수

#include <iostream>
#include <cstdio>

using namespace std;

int n, m, c, map[55][55], dp[55][55][55];


int solve(int y, int x, int k, int l)//(행,열,거쳐가야할 오락실의 개수, 최근에 방문한 오락실 번호)
{
	if (y == n && x == m)
	{
		if (k == 1 && map[y][x] > l)
			return 1;
		if (k == 0 && map[y][x] == 0)
			return 1;
		return 0;
	}
	if (y > n || x > m)
		return 0;
	if (dp[y][x][k] != -1)
		return dp[y][x][k];
	dp[y][x][k] = 0;
	if (map[y][x] != 0)
	{
		if (k > 0 && map[y][x] > l)
			dp[y][x][k] = (dp[y][x][k] + solve(y + 1, x, k - 1, map[y][x]) + solve(y, x + 1, k - 1, map[y][x])) % 1000007;
		else
			return 0;
	}
	else
		dp[y][x][k] = (dp[y][x][k] + solve(y + 1, x, k, l) + solve(y, x + 1, k, l)) % 1000007;
	return dp[y][x][k];
}

int main()
{
	int i, j, k, y, x;
	scanf("%d%d%d", &n, &m, &c);

	for (i = 0; i < 55; i++)
	{
		for (j = 0; j < 55; j++)
		{
			for (k = 0; k < 55; k++)
				dp[i][j][k] = -1;
		}
	}
	for (i = 1; i <= c; i++)
	{
		scanf("%d%d", &y, &x);
		map[y][x] = i;
	}
	for (i = 0; i <= c; i++)
		printf("%d ", solve(1, 1, i, 0));

	return 0;
}

pichulia 4년 전 1

가장 마지막에 방문한 오락실의 번호에 따라서 dp[y][x][k]값이 달라져야 하는데 그런 고려가 안되있습니다. 무조건 0이거나 무조건 어떤 값이 되버리네요.

leekh2002 4년 전 0

그부분을 고려못했네요.. 덕분에 해결했습니다 감사합니다!

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

문제

문제

출처

ICPC

반례를 못찾겠습니다...

leekh2002 4년 전 0

pichulia 4년 전 1

leekh2002 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말