백준[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;
}