Boj 11048) 이동하기

문제

백준 11048

설명

DFS, BFS 를 하면서 visits 부분에 현재 최댓값을 넣어서 처리하려고 했음.

근데 알고보니까 처음에 도착했지만 최적이 아닌 애는 자동으로 다음 탐색을 준비 또는 시작하게 되는 거임.

그 위치에서 가장 최적인 애만 다음 탐색을 진행해야하는데, visits 과는 달리 바로 작동하게 되는 것임.

이게 누적되면 시간초과가 뜨는 것임.

그래서 BFS, DFS 를 쓰려면 visits 체크단계랑 다음탐색 단계를 나눠서 진행해야하는데, 이럴거면 DP 씀.

시간 복잡도

O(n * m)

코드

int n, m;
int board[1001][1001];
int dp[1001][1001];

int main()
{
	fastio;

	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> board[i][j];

	dp[0][0] = board[0][0];
	for (int i = 1; i < n; i++)
		dp[i][0] = dp[i-1][0] + board[i][0];
	for (int j = 1; j < m; j++)
		dp[0][j] = dp[0][j - 1] + board[0][j];
	
	for (int i = 1; i < n; i++)
		for (int j = 1; j < m; j++)
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + board[i][j];

	cout << dp[n - 1][m - 1];
}