[BOJ] 11048번: 이동하기

11048번: 이동하기

풀이

간단히 바로 생각나는 점화식은
dp[i][j]=max(dp[i−1][j],dp[i−1][j−1],dp[i][j−1])dp[i][j] = max(dp[i - 1][j], dp[i - 1][j-1], dp[i][j-1])dp[i][j]=max(dp[i−1][j],dp[i−1][j−1],dp[i][j−1])인데 캔디 개수로 음수가 나올리가 없으므로 dp[i−1][j−1]dp[i-1][j-1]dp[i−1][j−1]을 도는 것은 사치다.

최대한 많이 얻어야 좋은 건데 바로 한 단계를 건너뛰는 것은 엄연한 사치다.
그래서 dp[i][j]=max(dp[i−1][j],dp[i][j−1])dp[i][j] = max(dp[i - 1][j], dp[i][j-1])dp[i][j]=max(dp[i−1][j],dp[i][j−1])까지 줄일 수 있다.

dp 배열을 1차원까지 줄일 수 있는데 위로 못 올라가기 때문에 가능한 것인데, dp[j - 1]은 dp[i][j - 1]의 최댓값, dp[j]은 dp[i][j]의 최댓값이 된다. 한 번 손으로 해보면 왜 그런지 알 수 있다.

코드

#include <iostream>
using namespace std;
inline int max(int a, int b) { return a > b ? a : b; }
int n, m, dp[1001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1, a; j <= m; ++j)
        {
            cin >> a;
            dp[j] = max(dp[j - 1], dp[j]) + a;
        }
    }
    cout << dp[m];
    return 0;
}