BOJ 2507 공주 구하기

BOJ 2507 공주 구하기

[분류 : 다이나믹 프로그래밍]

 

[풀이]

  [O(N^3) 메모리] 가장 간단하게 p번째 섬을 출발 경로 또는 귀환 경로에 포함할지를 판단하는 dp를 생각할 수 있다. 하지만 이는 메모리 O(N^3)를 잡아 먹기 때문에 불가능하다.

 

  [접근 아이디어] 이런 왕복문제의 경우 시작점에서 도착점으로 가는 경로를 생각하자. 즉, 시작점은 항상 하나고, 도착점도 항상 하나로 두고 그 상태에서 서로 다른 경로를 구하면 그것이 곧 갔다가 오는 경로를 모드 셈해주는 것과 같다.

  [도달 검사] 첫 번째 섬을 제외한 나머지 섬은 반드시 한 번만 밟을 수 있기 때문에 왕복을 위해선 서로 다른 경로 두 개를 구성할 수 있는 경우의 수로 문제를 변형할 수 있다. 단, 한 경로는 현재 섬에서 현재 섬보다 멀리 갈 수 있는 섬에 대해 검사가 필요하고, 반대로 다른 하나는 보다 멀리 있는 섬에서 현재 섬에 올 수 있는지에 대한 검사가 필요하다. 

  [경우의 수] 기저 사례로는 두 경로 모두 마지막 섬에 도달했을 때 경우가 존재하는지 알기 위해 마지막 섬과의 도달 가능성을 검토해야 한다.

  [경로 이동] 마지막 섬으로 가는 경로를 a에 저장하고, 마지막 섬에서 다시 돌아오는 경로를 b라고 하자. 섬 p(단, p>a, p>b)에 대해 a에 할당할 것인지 b에 할당할 것인지를 정한다. 또 p를 할당하지 않을 경우의 수 또한 고려해야한다. 단, 구간 (a, p) 또는 구간 (b, p)에 있는 섬들은 두 경로 어느쪽에도 할당하지 않아야 중복없이 계산할 수 있다.

  [중복] 이렇게하면 우리가 원하는 답×2가 나오게 되는데, 이유는 유일하게 마지막 섬만 두 경로가 포함할 수 있는데, 가령 a에 마지막 섬에 위치시키고 b를 마지막 섬에 위치 시키는 경우와 b를 먼저 마지막 섬에 위치시키고 a를 마지막 섬에 위치시키는 경우가 같은 경우임에도 셈을 따로 하기 때문이다. 2와 Modulo가 서로소라면 페르마의 소정리를 이용할 수 있겠지만 하필 1000이라서 아쉽게도 사용하지 못한다. 따라서 a 또는 b가 먼저 N-1에 도달하는 경우만 셈해주도록하면 중복을 제거할 수 있다.

 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_N = 500, MOD = 1e3;
struct _l { int d, p, r; } land[MAX_N];
bool operator<(const _l& a, const _l& b) { return a.d < b.d; }
int N, dp[MAX_N][MAX_N];
int rec(int a, int b) {
    if (a == N - 1 || b == N - 1)
        return a == N - 1 && land[N - 1].d <= land[a].d + land[a].p && land[N - 1].r && land[N - 1].d - land[N - 1].p <= land[b].d;
    int& ret = dp[a][b];
    if (ret != -1) return ret;
    int i, L = min(N - 1, max(a, b) + 1);
    ret = 0;
    for (i = L; i < N; i++) {
        if(land[i].d <= land[a].d + land[a].p)
            ret = (ret + rec(i, b)) % MOD;
        if (land[i].r && land[i].d - land[i].p <= land[b].d)
            ret = (ret + rec(a, i)) % MOD;
    }
    return ret;
}
int main() {
    memset(dp, -1, sizeof dp);
    int i;
    scanf("%d", &N);
    for (i = 0; i < N; i++)
        scanf("%d%d%d", &land[i].d, &land[i].p, &land[i].r);
    printf("%d", rec(0, 0));
    return 0;
}