[BAE/<JOON> 문제풀이] 2253. 점프

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

2253번: 점프

서론

특이하게 메모리 제한을 빡세게 걸어놨다. short 으로 하고 dp배열 계산식으로 할당해야 피해짐. 무식하게 10e7개 int 잡으면 안됨

풀이

현재 지점 i까지 올 수 있는 구간은 i / 2 ~ i - 1 까지다. i / 2 미만 지점에서는 점프거리를 늘리기만 해도 i에 닿을 수 없다.

마찬가지로 i에서 점프할 수 있는 최대 거리도 i다. 그 이상은 이전 단계에서 점프거리를 늘리기만해도 뛸 수 없다.

따라서 점화식은 아래와 같다.

DP[현재 지점][현재 지점에서 뛸 수 있는 점프거리] = 현재 시점까지 점프 횟수

현재 지점 : i

i로 오는 이전 지점 : j ( i / 2 ~ i - 1 )

DP[i][i - j + k] = DP[j][i - j] + 1

점프거리 변량 : k = -1 ~ 1 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll mod = 10e8 + 9;
struct p {
    int j, c;
};
const short sm = 32767;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m; vector<vector<short>> dp(n + 1);    
    for (int i = 1; i <= n; i++) {
        dp[i].resize(i + 1, sm);
    }
    for (int i = 1; i <= m; i++) {
        int t; cin >> t; dp[t][0] = 1;
    }
    dp[1][1] = 0;
    for (int i = 2; i <= n; i++) {
        if (dp[i][0] == 1) continue;
        for (int j = i / 2; j < i; j++) {
            if (i - j > j) continue;
            if (dp[j][i - j] != sm) {
                short nx = dp[j][i - j] + 1;
                for (int k = -1; k <= 1; k++) {
                    dp[i][i - j - k] = dp[i][i - j - k] < nx ? dp[i][i - j - k] : nx; 
                }
            }
        }
    }    
    short mn = sm;
    for (int i = 1; i <= n; i++) {
        if (dp[n][i] == sm) continue;
        mn = mn < dp[n][i] ? mn : dp[n][i];
    }
    cout << (mn == sm ? -1 : mn);
    return 0;
}