글 읽기 - 답이 계속 오류가 나네요

ygo22 7년 전 0

제 알고리즘은 dfs에 dp 메모제이션을 이용해서 가지치기를 하는것입니다.

예를 들면 대나무숲을 방문해서 dfs로 가장 최대로 살수있는 날을 찾아

다른 배열에 저장해놓습니다. 그래서 방문한곳에 다시 온다면 그 자리의

최대값+1 을 넘겨줍니다. 이 방식으로 가지치기를 했습니다만 계속 틀린답이네요

반례를 찾기 힘들어서 질문글을 남깁니다.

아..마지막에 음수랑 0도 정수안에 포함되나 해서 다 만들어놓은거에 추가 구현하여

코드가 지저분합니다. 제가 놓친 부분이 무엇일까요

#include<cstdio>
#include<stdio.h>

int map[500][500] = { 0 };
int visit[500][500] = { 0 };

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

int s_max = 0;
int t_max = 0;

int gogo(int x, int y, int num) {
	if (map[x][y] <= 0) return 0;
	if (visit[x][y] != 0) {
		return visit[x][y] + 1;
	}
	num = num + 1;
	int n = num;
	if (s_max < n)s_max = n;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (map[nx][ny] > map[x][y]) {
			n = gogo(nx, ny, n);
			if (s_max < n)s_max = n;
			n = num;
		}
	}
	return n;
}

int main() {
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			s_max = 0;
			int n = gogo(i, j, 0);
			visit[i][j] = s_max;
			if (s_max > t_max)t_max = s_max;
		}
	}

	printf("%d\n", t_max);
	return 0;
}

game2k 7년 전 0

입력에 음수, 0이 들어올 경우 틀리도록 했는데 정답인걸 봐서 입력은 전부 양수인것 같네요

game2k 7년 전 1

일단 배열의 범위를 체크해 보세요.

(0, 0) 부터 체크할 경우 if (map[nx][ny] > map[x][y]) 에서 nx = -1, ny = 0 이 들어가요.

game2k 7년 전 2

4
16 15 14 13
9 10 11 12
8 7 6 5
1 2 3 4

답 16

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

문제

문제

출처

ICPC

답이 계속 오류가 나네요

ygo22 7년 전 0

game2k 7년 전 0

game2k 7년 전 1

game2k 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말