백준[11048] - 이동하기

문제

백준 11048 문제 보기

접근 방법

다아나믹프로그램을 활용해서 문제를 해결할 수 있다. 먼저 조건을 보면 이동하는 경우는 총 3가지로 오른쪽, 아래, 대각선 방향으로 이동이 가능하다.
가장 위쪽 행과 가장 왼쪽 열은 이전 사탕의 갯수를 그대로 더하고 나머지 가운데 부분은 접근 가능한 방향에서의 최대값을 가지는 식으로 코드를 작성했다.

  • 가장 위쪽
    dp[i][j] = map[i][j] + dp[i][j-1];
  • 가장 왼쪽
    dp[i][j] = map[i][j] + dp[i-1][j];
  • 나머지 영역
    dp[i][j] = map[i][j] + max(dp[i-1][j], max(dp[i][j-1], dp[i-1][j-1]));

코드

#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
int map[1000][1000];
int dp[1000][1000];
int main() {
cin >> N >> M;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j ++) {
cin >> map[i][j];
}
}
dp[0][0] = map[0][0];
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j ++) {
// 가장 위쪽
if(i == 0 && j - 1 >= 0) {
dp[i][j] = map[i][j] + dp[i][j-1];
}
// 가장 왼쪽
if(j == 0 && i - 1 >= 0) {
dp[i][j] = map[i][j] + dp[i-1][j];
}
// 나머지 영역
if(i != 0 && j != 0) {
dp[i][j] = map[i][j] + max(dp[i-1][j], max(dp[i][j-1], dp[i-1][j-1]));
}
}
}
cout << dp[N-1][M-1];
return 0;
}
Share