글 읽기 - 틀린이유를 모르겠어요

qktlf789456 3년 전 0

시간초과는 이해해도 틀린이유가 이해가안갑니다 ㅠ 코드에서 시간초과가아닌 어디부분이 틀렸을까요?

#include <iostream>
#include <algorithm>
#include <math.h>

#define EMPTY -215214

using namespace std;


/*
ios_base::sync_with_stdio(0);
cin.tie(0);
3
3 2 7
4 2 6
5 3 8
U 1 2
D 3 2
U 1 2
*/

int n;

int** matrix;
int** dp;
int cur_max = 0;

int get_max(int a, int b)
{
	if (a == 0 && b == 0)
		return 0;

	if (a == 0)
		return dp[a][b - 1];
	else if (b == 0)
		return dp[a - 1][b];

	return dp[a - 1][b] >= dp[a][b - 1] ? dp[a - 1][b] : dp[a][b - 1];
}


void update_dp(int x, int y, int value)
{
	if (x >= n || y >= n)
		return;


	int pre_dp = dp[x][y];

	int aft_dp = matrix[x][y] + get_max(x, y);



	if (pre_dp != aft_dp) //갱신해야하는경우
	{
		dp[x][y] = aft_dp;
		cur_max += value;

		update_dp(x + 1, y, value);
		update_dp(x, y + 1, value);
	}

}

void dfs(int x, int y, int value)
{
	matrix[x][y] += value;
	dp[x][y] += value;
	cur_max += value;

	update_dp(x + 1, y, value);
	update_dp(x, y+1, value);
}

void view()
{
	cout << "\n\n\n";
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << "[" << dp[i][j] << "]";
		}
		cout << "\n";
	}
}


int main()
{
	cin >> n;
	matrix = new int*[n];
	dp = new int*[n];
	for (int i = 0; i < n; i++)
	{
		matrix[i] = new int[n];
		dp[i] = new int[n];
		for (int j = 0; j < n; j++)
		{
			cin >> matrix[i][j];
			dp[i][j] = matrix[i][j];
		}
	}


	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			dp[i][j] = matrix[i][j] + get_max(i, j);
			cur_max += dp[i][j];
		}
	}

	cout << cur_max << "\n";
	
	char alpha;
	int a, b;
	for (int i = 0; i < n; i++)
	{
		cin >> alpha >> a >> b;

		if (alpha == 'U')
			dfs(a - 1, b - 1, 1);
		else
			dfs(a - 1, b - 1, -1);

		cout << cur_max ;
		
		if (i != n - 1)
			cout << "\n";



		//view();
	}


	return 0;
}

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

문제

문제

출처

ICPC

틀린이유를 모르겠어요

qktlf789456 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말