[Gold IV] 가희와 비행기 - 22236

[문제 위치]

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

[문제 풀이]

이 문제는 DP를 이용해 조건을 만족하는 비행 경로의 개수를 세는 문제이다.
문제가 요구하는 것은 총 거리 d를 이동하는 동안, 매 순간 고도가 정확히 1씩만 변하고(±1), 출발과 도착을 제외하고는 고도 0에 닿지 않는 경로의 개수(모듈러 m)이다.
중간에 고도 0이 되는 순간은 “착륙”이므로 그 경로는 불가능하다.

이를 위해 dp[i][h]를 다음처럼 정의한다.

• dp[i][h] = “총 i번 이동했을 때(=거리 i), 고도가 h이고, 도착 전까지는 고도 0에 한 번도 닿지 않은 경로의 수”

이제 전이를 생각해보자.

한 번 이동할 때 고도는 반드시 ±1만큼 변한다.
즉, i번째에 고도 h에 도착하려면, 바로 이전(i-1)에는

• h-1에 있다가 올라오거나
• h+1에 있다가 내려와야 한다.

따라서 점화식은 다음과 같다.

• dp[i][h] = dp[i-1][h-1] + dp[i-1][h+1] (mod m)

여기서 중요한 제약이 하나 더 있다.

• 도착(i = d) 전에는 고도 0이면 안 되므로, i < d인 동안은 h = 0 상태를 만들지 않는다.
  • 구현에서는 아예 h ≥ 1만 채우고, dp[*][0]은 0으로 두면 된다.

처음 고도는 0인데, 중간에 0이면 안 되므로 첫 이동은 무조건 상승밖에 없다.

• dp[1][1] = 1

마지막(d번째)에는 반드시 고도 0으로 착륙해야 한다.
고도 변화가 ±1이므로, 마지막 직전(d-1) 고도는 반드시 1이어야만 0으로 내려올 수 있다.

• 정답 = dp[d-1][1] (mod m)

점화식이 항상 더 작은 i-1만 참조하므로 dp[1]부터 dp[d-1]까지 바텀업으로 채우면 된다.
또한 한 행을 계산할 때 직전 행만 필요하므로, 2개의 1차원 배열로 굴려서 메모리를 O(d)로 줄일 수 있다.

아래는 이를 구현한 코드이다.

#include <iostream>
#include <vector>
using namespace std;

#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);

int main() {
    FASTIO

    int d;
    long long m;
    cin >> d >> m;

    // d가 홀수면 0으로 돌아올 수 없음 (문제에선 d가 짝수로 주어지는 편)
    if (d < 2 || (d & 1)) {
        cout << 0 << '\n';
        return 0;
    }

    vector<long long> prev(d + 3, 0), cur(d + 3, 0);

    // 첫 이동: 고도 0 -> 1 (중간에 0이면 안 되므로 시작은 항상 상승)
    prev[1] = 1; // i=1, h=1

    // i = 2 .. d-1 (도착 전까지는 고도 0 금지 => h는 1 이상만 유지)
    for (int i = 2; i <= d - 1; i++) {
        fill(cur.begin(), cur.end(), 0);
        for (int h = 1; h <= i; h++) {
            long long val = prev[h - 1] + prev[h + 1];
            cur[h] = val % m;
        }
        prev.swap(cur);
    }

    // 마지막 한 칸은 (d-1, 1) -> (d, 0) 착륙만 가능
    cout << (prev[1] % m) << '\n';
    return 0;
}