11048 이동하기

11048. 이동하기 / c++ / Silver2 / 21분

문제

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

1. 1,1 ~ N,M까지의 미로에 각 칸마다 사탕이 0~100개 놓여있다.
2. 준규는 1,1부터 N,M까지이 이동할 때, ‘아래/오른쪽/오른쪽아래대각선’으로만 이동할 수 있다.
3. N,M에 도착했을 때, 얻을 수 있는 사탕의 최대 갯수는?

접근 방식

동적 프로그래밍

1. 한칸이라도 더 들러야 이득인 상황이라, 오른쪽 아래 대각선 이동은 고려안함
2. 현재칸에서 윗칸과 오른쪽 칸 중 더 큰 값을 구하고 그 값과 현재 칸의 사탕값을 더함
3. dp[N][M] 출력

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
using namespace std;

inline int MAX(int A, int B) { return A > B ? A : B; }

int N, M;
int arr[1'001][1'001];
int dp[1'001][1'001] = {};

int dy[2] = { 0, -1 };
int dx[2] = { -1, 0 };

int DP(int n, int m)
{
    if (dp[n][m] == 0)
    {
        int maxNum = 0;
        for (int i = 0; i < 2; ++i)
        {
            int nextY = n + dy[i];
            int nextX = m + dx[i];
            if (nextY < 1 || nextY > N || nextX < 1 || nextX > M) continue;
            int nextNum = DP(nextY, nextX);
            if (nextNum == -1) continue;
            maxNum = MAX(maxNum, nextNum);
        }
        dp[n][m] = arr[n][m] + maxNum;
        if (dp[n][m] == 0) dp[n][m] = -1;
    }

    return dp[n][m];
}

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 >> arr[i][j];
        }
    }

    int answer = DP(N, M);
    if (answer == -1) cout << "0\n";
    else cout << answer << '\n';

    return 0;
}

다시 생각해 볼 점

1. 시간이 더 빠른 코드를 살펴보니, 아래와 같이 경우를 나누었다.
   1. 맨 윗줄의 경우 그보다 윗줄은 없으므로 무조건 왼쪽 값 +
   2. 맨 왼쪽줄의 경우 그보다 왼쪽 줄은 없으므로 무조건 윗쪽 값 +
   3. 그 외의 줄은 윗쪽과 왼쪽 줄의 값을 비교하여 큰 값 +
2. 이 것을 board[n][m]을 입력받을 때 바로 수행하면, dp[n][m]을 따로 만들지 않아도 돼서 메모리 효율도 올라가고, 시간도 줄었다.
3. 이렇게 입력 받자마자 바로 계산하는 방법을 항상 염두해둬야겠다.