BaekJoon 11048번: 이동하기(C++)

https://www.acmicpc.net/problem/11048

11048번: 이동하기

풀이법

1) n과m의 크기가 1000이 될 수 있기에, dfs나 bfs를 이용하면 시간 초과가 발생할 수 있어 DP로 문제를 해결했다.

2) 기존에 입력받은 배열을 제외하고 ans 배열을 만들어서, 현재 index에서의 최대 값을 찾는 저장하는 배열을 만들었다.

시작 index가 1,1 이고, 0행과 1열은 선언시 부터 0으로 초기화 되어있기에, 점화식을 다음과 같이 세웠다.

3) 실버1 문제 치고는 굉장히 직관적으로 이해가 쉬우니 꼭 도전해서 맞추며 공부하는 것을 추천한다.

for (int i = 1; i <= n; i++)
{
	for (int j = 1; j <= m; j++)
	{
		ans[i][j] = max(ans[i-1][j], ans[i][j-1]) + arr[i][j];
	}
}

#include <string>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <math.h>
#include <map>
#define INF 987654321
using namespace std;

int n, m;
int arr[1001][1001];
int ans[1001][1001];
int vx[2] = { 1,0};
int vy[2] = { 0,1 };
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <=n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> arr[i][j];
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			ans[i][j] = max(ans[i-1][j], ans[i][j-1]) + arr[i][j];
		}
	}
	cout << ans[n][m];
}