글 읽기 - 채점 70% 쯤에서 틀렸습니다가 되는데 뭐가 틀린건가요?

ahn4685 7년 전 0

내리막만 기준으로 하길래 위쪽으로 가는 부분은 검증을 하지 않는 걸로 하여서 출력값도 정상적으로 출력되었습니다.

뭐가 문제인걸까요?

#include<iostream>
#include<vector>
#include<array>

using namespace std;

array<array<int, 501>, 501> arr;
array<int, 4> dx = { 0,0,-1,1 };
array<int, 4> dy = { 0,1,0,0 };
array<array<int, 501>, 501> dp;
int m, n;

int solve(int y, int x)
{
	if (y == m && x == n) return 1;
	if (dp[y][x] != 0) return dp[y][x];
	for (int i = 1; i < 4; i++)
	{
		if (x + dx[i] <= n && y + dy[i] <= m && x + dx[i] > 0 && arr[y + dy[i]][x + dx[i]] < arr[y][x])
			dp[y][x] += solve(y + dy[i], x + dx[i]);		
	}
	return dp[y][x];
}
int main(void)
{
	int i, j;

	cin >> m >> n;

	for (i = 1; i <= m; i++)
	{
		for (j = 1; j <= n; j++)
			cin >> arr[i][j];
	}

	cout<<solve(1, 1)<<endl;

	return 0;
}

haja 7년 전 1

이 문제에서 내리막길이라는 건 방향이 아니라 숫자가 더 작은 곳으로 갈 수 있다는 말인 거 같습니다.

yclock 7년 전 0

반례입니다.

/*
Input:
3 5
55 99 49 48 47
54 99 50 99 46
53 52 51 99 45

Correct Output:
1

Your Output:
0
*/

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

문제

문제

출처

ICPC

채점 70% 쯤에서 틀렸습니다가 되는데 뭐가 틀린건가요?

ahn4685 7년 전 0

haja 7년 전 1

yclock 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말