백준 22236번: 가희와 비행기 [C++]

작성일 | In
골드 IV 골드 IV

문제

가희와 비행기

발상

비행기가 $i$만큼 이동했을때, 경우의 수는 $i-1$만큼 이동했을때 에서 두가지로 나뉜다는 것을 알 수 있습니다. 이에 착안해 점화식을 세워 DP로 풀 수 있습니다.

비행기가 날아갈 때 이동한 거리를 $i$, 그 때의 고도를 $j$라고 합시다. 이때 경우의 수를 $dp[i][j]$라고 하면
$dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]$임을 이용해 쉽게 풀 수 있습니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll dp[4001][4001];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int d, m;
    cin >> d >> m;
    fill(&dp[0][0], &dp[4000][4001], 0);
    dp[1][1] = 1;
    for (int i = 2 ; i < d ; i++) {
        for (int j = 1 ; j <= i ; j++) {
            if (0 < j - 1) dp[i][j] += dp[i-1][j-1] % m;
            if (j + 1 <= d) dp[i][j] += dp[i-1][j+1] % m;
        }
    }

    cout << dp[d-1][1] % m;

    return 0;
}

여담

사실 점화식은 엄청 빨리 떠올렸는데 답이 int범위를 벗어날 거란 생각을 못해서 4번이나 틀렸습니다… ㅠㅠ
앞으로 경우의 수 구하는 문제는 int 범위를 벗어나지는 않는지 꼼꼼하게 체크해야겠습니다.

백준 22236번: 가희와 비행기 [C++]