[BOJ11048] 이동하기

[BOJ11048] 이동하기

문제링크

문제설명

• 배열의 1,1에서 시작하여 N,M까지 이동할 때, 이동하며 지나온 배열값의 합 중 최대를 출력하는 문제이다.
• 현재 위치가 r,c라고 할때 (r+1,c), (r+1,c+1), (r,c+1)로 이동할 수 있다.

코드리뷰

• 처음에는 최대값을 구하는 문제지만, 이동할수 있는 방향을 봤을 때 순환이 생기지 않기때문에 bfs를 통해 ‘보급로’ 문제처럼 풀었다. 110ms 안에 답이 나오긴 했다.
• dp를 이용하여, 반복문을 쭉 보면서 점화식을 이용하여 풀 수 있다는 것을 알게되었다.
• dp[i][j]= max{dp[i-1][j-1]+board[i][j], dp[i-1][j]+board[i][j],dp[i][j-1]+board[i][j]} 점화식을 알 수 있다.
• 이 점화식을 이용하여 dp배열을 쭉 채운 후, dp[N][M]을 출력하면 된다.

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int board[1005][1005];
int dp[1005][1005];


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> board[i][j];
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			dp[i][j] = max(dp[i-1][j-1]+board[i][j],max(dp[i][j - 1] + board[i][j], dp[i - 1][j] + board[i][j]));
		}
	}
	cout << dp[N][M] << '\n';
	return 0;
}