글 읽기 - 이 풀이가 틀린 이유가 무엇인가요?

zzaz1012 1년 전 0

점화식이 왜 틀렸는지 모르겠네요... 반례나 이유를 설명해주시면 정말루 감사하겠습니다.

#include <bits/stdc++.h>
using namespace std;

int arr[1000][1000];
int dp[1000][1000];
int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	
	int M, N;
	cin >> M >> N;
	
	for (int i=0;i<M;i++)
	{
		for (int j=0;j<N;j++)
		{
			cin >> arr[i][j];
			if (arr[i][j]==1 || arr[i][j]==2)
			{
				dp[i][j]=-1;
			}
			else
			{
				dp[i][j]=arr[i][j];
			}
		}
	}
	for (int i=0;i<M;i++)
	{
		if (dp[i][0]!=-1)
		{
			dp[i][0]=1;
		}
	}
	for (int i=0;i<N;i++)
	{
		if (dp[0][i]!=-1)
		{
			dp[0][i]=1;
		}
	}
	for (int i=1;i<M;i++)
	{
		for (int j=1;j<N;j++)
		{
			if (dp[i][j]==-1)
			{
				continue;
			}
			if (dp[i-1][j-1]==-1 || dp[i-1][j]==-1 || dp[i][j-1]==-1)
			{
				dp[i][j]=1;
			}
			else
			{
				if (dp[i-1][j-1]==dp[i-1][j] && dp[i-1][j]==dp[i][j-1])
				{
					dp[i][j]=dp[i-1][j-1]+1;
				}
				else
				{
					int k = max(dp[i-1][j],dp[i][j-1]);
					dp[i][j]=max(k,dp[i-1][j-1]);
				}
			}
		}
	}
	
	int maxx=0;
	for (int i=0;i<M;i++)
	{
		for (int j=0;j<N;j++)
		{
			if (dp[i][j]>maxx)
			{
				maxx=dp[i][j];
			}
		}
	}
	cout << maxx;
	
	
	return 0;
}

zzaz1012 1년 전 0

자문자답합니다.

dp 테이블이

3 1

1 ?

인 경우를 생각해보면 틀린 점화식이네요

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

문제

문제

출처

ICPC

이 풀이가 틀린 이유가 무엇인가요?

zzaz1012 1년 전 0

zzaz1012 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말