글 읽기 - 배열 크기 +1??

songgj123 7년 전 0

제 코드입니다.

DP 사용해서 풀었는데

답이 틀려서

배열 크기를 MAX + 1 해주니 답이 맞더군요

왜 최대 크기는 MAX인데 +1을 해줘야 답이 되나요??

그동안 그냥 넘어갔던 것이 궁금해서 질문합니다.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX = 501;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int n;
int arr[MAX][MAX];
int cache[MAX][MAX];
int visited[MAX][MAX];

bool allowXY(int x, int y, int d)
{
	int nx = x + dx[d];
	int ny = y + dy[d];

	if(nx < 0 || nx > n || ny < 0 || ny > n)
	{
		return false;
	}
	if(arr[nx][ny] <= arr[x][y])
	{
		return false;
	}
	return true;
}

int panda(int x, int y)
{
	int& ret = cache[x][y];
	int flag = 0;

	if(ret != -1)
	{
		return ret;
	}

	ret = 1;

	for(int i = 0; i < 4; i++)
	{
		if(allowXY(x, y, i))
		{
			visited[x + dx[i]][y + dy[i]] = 1;
			ret = max(ret, panda(x + dx[i], y + dy[i]) + 1);
			visited[x + dx[i]][y + dy[i]] = 0;
		}
	}
	return ret;
}

int solve()
{
	int ret = 0;

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			visited[i][j] = 1;
			ret = max(ret, panda(i, j));
			visited[i][j] = 0;
		}
	}
	return ret;
}

int main()
{
	cin>>n;

	memset(cache, -1, sizeof(cache));
	memset(visited, 0, sizeof(visited));

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			cin>>arr[i][j];
		}
	}
	cout<<solve()<<endl;

	return 0;
}

qja0950 7년 전 0

아마 이 부분을 고치면 해결되실 것 같습니다. (MAX로 쓰셔도 AC가 나올 것 같습니다.)

	if(nx < 0 || nx > n || ny < 0 || ny > n)
        
    =>
        
	if(nx < 0 || nx >= n || ny < 0 || ny >= n)

songgj123 7년 전 1

아 그렇네요

조건이 잘못되서

MAX가 500이면 안되는 거였네요

감사합니다

qja0950 7년 전 1

여담이지만, 잘못되서 -> 잘못되어서 or 잘못돼서 입니다!

즐거운 프로그래밍하세욥 :)

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

문제

문제

출처

ICPC

배열 크기 +1??

songgj123 7년 전 0

qja0950 7년 전 0

songgj123 7년 전 1

qja0950 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말