튜브의 소개팅 - level 4

해결방법

고려해야 변수는 y, x, d(거리)이다. 따라서 3차원 배열로 dp를 정의했다.

ll dp[51][51][2510];

점화식은 아래와 같이 된다. newy, newx는 다음번에 이동할 좌표를 의미한다. 다음 좌표는 해당 좌표의 +1이므로 d+1번째에 저장한다. 이전까지의 s + time_map[y][x]를 저장하면 된다.
$$ dp[newy][newx][d+1] = min(dp[newy][newx][d+1], dp[y][x][d] + time_map[y][x]) $$

당연히 수다시간은 제한이 있으므로 제한 시간 넘으면 못가게 해야 한다.

if(dp[y][x][d] + time_map[y][x] <= s)
    dp[newy][newx][d+1] = min(dp[newy][newx][d+1],dp[y][x][d] + time_map[y][x]);

전체코드

#include <vector>
using namespace std;
typedef long long ll;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
ll dp[51][51][2510];
const ll inf = (ll)1 << 31;
vector<int> solution(int m, int n, int s, vector<vector<int>> time_map) {
    vector<int> answer;
    for(int y = 0; y <= 50; ++y)
        for(int x = 0; x <= 50; ++x)
            for(int i = 0; i < 2510; ++i)
                dp[y][x][i] = inf;
    dp[0][0][0] = 0;
    for(int d = 0; d < 2500; ++d)
        for(int y = 0; y < m; ++y)
            for(int x = 0; x < n; ++x) {
                if(time_map[y][x] == -1) continue;
                for(int i = 0; i < 4; ++i) {
                    int newy = y + dy[i];
                    int newx = x + dx[i];
                    if(newy < 0 || newx < 0 || newy >= m || newx >= n) continue;
                    if(dp[y][x][d] + time_map[y][x] <= s)
                        dp[newy][newx][d+1] = min(dp[newy][newx][d+1],dp[y][x][d] + time_map[y][x]);
                }
            }
    for(int i = 0; i < 2500; ++i)
        if(dp[m-1][n-1][i] != inf) {
            answer = {i, (int)dp[m-1][n-1][i]};
            break;
        }
    return answer;
}