백준 11048 이동하기(c++)

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

11048번: 이동하기

이 문제는 오른쪽, 아래쪽, 대각선으로 이동하여 가져올 수 있는 사탕의 개수의 최댓값을 구하는 문제입니다. 다양한 방식으로 풀 수 있는데, 저는 Top-down 방식(재귀)보다 Bottom-Up 방식이 익숙해서 Bottom-up으로 풀었습니다. 

기본 로직은 이러합니다.

dp[i][j] = max(max(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + a[i][j];

이동하면서, 값을 누적시켜야 하는데, 아래쪽, 오른쪽, 대각선 중 어느 방향으로 이동하는 것이 최댓값을 가지는지 check해주고 기존 입력받은 값을 누적시켜 주면 됩니다. 

 

<코드>

#include <iostream>
#include <algorithm>

using namespace std;
int dp[1001][1001];
int a[1001][1001];
//Top-down
int go(int i, int j)
{
    if(i< 1|| j < 1) return 0;
    dp[i][j] = max(go(i-1, j), go(i,j-1)) + a[i][j];
    return dp[i][j];
}
int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
        }
    }

    // Tabulation, Bottom-up 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            dp[i][j] = max(max(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + a[i][j];
        }
    }
    cout << dp[n][m] << '\n';

    //Tabulation, Bottom-up
    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]) + a[i][j];
        }
    }
    cout << dp[n][m] << '\n';

    dp[1][1] = 0;
    dp[2][1] = 0;
    dp[1][2] = 0;
    //Bottom-up
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (dp[i][j + 1] < dp[i][j] + a[i][j + 1])
            {
                dp[i][j + 1] = dp[i][j] + a[i][j + 1];
            }
            if (dp[i + 1][j] < dp[i][j] + a[i + 1][j])
            {
                dp[i + 1][j] = dp[i][j] + a[i + 1][j];
            }
            if (dp[i + 1][j + 1] < dp[i][j] + a[i + 1][j + 1])
            {
                dp[i + 1][j + 1] = dp[i][j] + a[i + 1][j + 1];
            }
        }
    }
    cout << dp[n][m]<<'\n';
    cout<<go(n,m)<<'\n';
}