BOJ 11057 해설 C++

2021-11-14 201 words One minute

Table of Contents

접근 방법

2차원 적으로 접근해보겠습니다. arr[i][j] 는 길이가 i이고 j로 끝나는 숫자의 갯수를 의미합니다. 아래와 같이 표를 그려보면 arr[i][j] = arr[i-1][j] + arr[i][j-1] 이라는 점화식을 유도해 낼 수 있습니다.

$$\begin{table}\centering\begin{tabular}{|c|l|r|r|}\hline11&12&13&14\\hline21&22&23&24\\hline\end{tabular}\end{table}$$

코드

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>

#define endl '\\n'

#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

/* - GLOBAL VARIABLES ---------------------------- */
int DP[1001][11];
/* ----------------------------------------------- */

#define SUBMIT
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

#ifndef SUBMIT
    (void)!freopen("input.txt", "r", stdin);
    cout << "# From the test case" << endl;
#endif
    int N; cin >> N;
    int mod = 10007;

    for(int i = 1; i <= 1000; ++i) {
        int sum = 1;
        DP[i][0] = 1;
        for(int j = 1; j <= 9; ++j) {
            DP[i][j] = ((DP[i-1][j] % mod) + (DP[i][j-1] % mod)) % mod;
            sum = ((sum % mod) + (DP[i][j] % mod)) % mod;
        }
        DP[i][10] = sum;
    }

    cout << DP[N][10] << endl;
    return 0;
}