무한부스터 17391

문제

접근 방법

오른쪽 밑으로 가는 것이 목표이기에 방향은 일정하다.
DP를 활용할 수 있다.
특정 지점을 최소로 도착하는 방법은 출발지에서 해당 지점으로 도착할 수 있을 때 최소의 값을 갱신시켜 주는 것이다. (지금의 값+1하는 것이 나은지 이전의 값을 유지하는 것이 나은지)

코드

#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector<vector<int>> map, dp;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    map = dp = vector<vector<int>>(N, vector<int>(M, N * M + 1));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            cin >> map[i][j];
    dp[0][0] = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            for (int k = 1; k <= map[i][j]; ++k)
            {
                if (i + k < N)
                    dp[i + k][j] = min(dp[i + k][j], dp[i][j] + 1);
                if (j + k < M)
                    dp[i][j + k] = min(dp[i][j + k], dp[i][j] + 1);
            }
    cout << dp[N - 1][M - 1];
    return 0;
}

풀이

부스터는 직선으로만 가는 것인데 범위 내에 있는 곳을 모두 포함하는 줄 알았다.