글 읽기 - 제가 간과한 부분이 있을까요?

sejungpk 6년 전 0

1. 첫줄에서 동쪽에서 쭉 dp 구하고 (최대값은 무조건 다음 상태인 경우라 생각하고 구했고 2->2와 같이 다음 상태가 아닌 경우 이전경우를 map에 저장하고 dp는 증가시키기 않습니다)
2. 세로 첫줄 아래쪽으로 쭉 dp 구한 후 위와 동일
3. 그리고 1,1부터 위에서 온경우와 왼쪽에서 온 dp에서 우유 상태가 담 상태면 1을 더해주는 식으로 해서 max 값을 저장했습니다

제가 간과한 부분이 있을까요?

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

int N;
int map[1001][1001];
int dp[1001][1001];

int main(void)
{
	cin >> N;
	for (int n = 0; n < N; n++)
	{
		for (int m = 0; m < N; m++)
		{
			cin >> map[n][m];
		}
	}

	if (map[0][0] == 0)
	{
		dp[0][0] = 1;
		for (int i = 1; i < N; i++)
		{
			if ((map[0][i - 1] + 1) % 3 == map[0][i])
			{
				dp[0][i] = dp[0][i - 1] + 1;
			}
			else
			{
				dp[0][i] = dp[0][i - 1];
				map[0][i] = map[0][i - 1];
			}
		}

		for (int i = 1; i < N; i++)
		{
			if ((map[i - 1][0] + 1) % 3 == map[i][0])
			{
				dp[i][0] = dp[i - 1][0] + 1;
			}
			else
			{
				dp[i][0] = dp[i - 1][0];
				map[i][0] = map[i - 1][0];
			}
		}

		int i = 0;

		for (int i = 1; i < N; i++)
		{
			for (int j = 1; j < N; j++)
			{
				if (map[i][j] == (map[i - 1][j] + 1) % 3)
				{
					if (map[i][j] == (map[i][j - 1] + 1) % 3)
					{
						dp[i][j] = max(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
					}
					else
					{
						dp[i][j] = max(dp[i - 1][j] + 1, dp[i][j - 1]);
						if (dp[i][j] == dp[i][j - 1])
							map[i][j] = map[i][j - 1];
					}
				}
				else
				{
					if (map[i][j] == (map[i][j - 1] + 1) % 3)
					{
						dp[i][j] = max(dp[i - 1][j], dp[i][j - 1] + 1);
						if (dp[i][j] == dp[i-1][j])
							map[i][j] = map[i-1][j];
					}
					else
					{
						dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
						if (dp[i][j] == dp[i][j - 1])
							map[i][j] = map[i][j - 1];
						else
							map[i][j] = map[i-1][j];
					}
				}
			}
		}
	}
	cout << dp[N - 1][N - 1] << endl;
	return 0;
}

djm03178 6년 전 0

1 0

0 0

sejungpk 6년 전 0

@djm03178

아 제가 그부분도 수정을 해서 제출했는데 틀렸다고 나왔습니다 ㅠㅠㅠㅠㅠㅠ

djm03178 6년 전 0

그렇게만 말씀하시면 제대로 고친 건지 제가 알 수가 없죠. 고친 코드를 다시 올려주세요.

sejungpk 6년 전 0

0,0이 0일때만 되고 0이 아니면 그냥 0을 출력하게 했습니다.

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

int N;
int map[1001][1001];
int dp[1001][1001];

int main(void)
{
	cin >> N;
	for (int n = 0; n < N; n++)
	{
		for (int m = 0; m < N; m++)
		{
			cin >> map[n][m];
		}
	}

	if (map[0][0] == 0)
	{
		dp[0][0] = 1;
		for (int i = 1; i < N; i++)
		{
			if ((map[0][i - 1] + 1) % 3 == map[0][i])
			{
				dp[0][i] = dp[0][i - 1] + 1;
			}
			else
			{
				dp[0][i] = dp[0][i - 1];
				map[0][i] = map[0][i - 1];
			}
		}

		for (int i = 1; i < N; i++)
		{
			if ((map[i - 1][0] + 1) % 3 == map[i][0])
			{
				dp[i][0] = dp[i - 1][0] + 1;
			}
			else
			{
				dp[i][0] = dp[i - 1][0];
				map[i][0] = map[i - 1][0];
			}
		}

		int i = 0;

		for (int i = 1; i < N; i++)
		{
			for (int j = 1; j < N; j++)
			{
				if (map[i][j] == (map[i - 1][j] + 1) % 3)
				{
					if (map[i][j] == (map[i][j - 1] + 1) % 3)
					{
						dp[i][j] = max(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
					}
					else
					{
						dp[i][j] = max(dp[i - 1][j] + 1, dp[i][j - 1]);
						if (dp[i][j] == dp[i][j - 1])
							map[i][j] = map[i][j - 1];
					}
				}
				else
				{
					if (map[i][j] == (map[i][j - 1] + 1) % 3)
					{
						dp[i][j] = max(dp[i - 1][j], dp[i][j - 1] + 1);
						if (dp[i][j] == dp[i - 1][j])
							map[i][j] = map[i - 1][j];
					}
					else
					{
						dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
						if (dp[i][j] == dp[i][j - 1])
							map[i][j] = map[i][j - 1];
						else
							map[i][j] = map[i - 1][j];
					}
				}
			}
		}
		cout << dp[N - 1][N - 1] << endl;
	}
	else
		cout << 0 << endl;

	return 0;
}

djm03178 6년 전 0

저 예시의 정답이 0이 아닙니다. 1이 정답입니다.

djm03178 6년 전 0

문제 어디에도 "(1, 1)에 있는 우유를 반드시 마실 수 있어야 한다" 같은 조건은 없습니다.

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

문제

문제

출처

ICPC

제가 간과한 부분이 있을까요?

sejungpk 6년 전 0

djm03178 6년 전 0

sejungpk 6년 전 0

djm03178 6년 전 0

sejungpk 6년 전 0

djm03178 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말