글 읽기 - 1937번 질문있습니다! dp

ace30126 7년 전 0

한줄한줄 검사하면서 주위보다 높으면 주위까지 올수있는 최대수 +1 을 하는 아이디어로 접근했는데, 틀렸다네요 ㅠㅠ 어디가 잘못된지 알려주십쇼!

#include <stdio.h>
#define max(x,y) x>y ? x:y

int a[555][555];
int d[555][555];

int main(void)
{
	int i,j;
	int n;
	int biggest=0;
	int de=-1;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
    
	for(i=0;i<556;i++){
		a[0][i]=1000000;
		a[i][0]=1000000;
	}
	
	while(biggest != de){
		de=biggest;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++){
			if(a[i][j]>a[i-1][j])
				d[i][j]=max(d[i][j],d[i-1][j]+1);
			if(a[i][j]>a[i+1][j])
				d[i][j]=max(d[i][j],d[i+1][j]+1);
			if(a[i][j]>a[i][j-1])
				d[i][j]=max(d[i][j],d[i][j-1]+1);
			if(a[i][j]>a[i][j+1])
				d[i][j]=max(d[i][j],d[i][j+1]+1);
			biggest=max(biggest,d[i][j]);
			}
	}
	printf("%d",de);
	return 0;
}

zlzmsrhak 7년 전 0

반례입니다.

while문 조건이 max 값이 바뀌지 않으면 끝내는 것으로 구현되어있는데, 그 부분에서 반례가 있을 수 있습니다.

3
1 4
2 5

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

문제

문제

출처

ICPC

1937번 질문있습니다! dp

ace30126 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말