π£ λ¬Έμ μ΄ν΄
1. 2234μ 3678, 11119 μ κ°μ΄ μΈμ ν μκ° κ°κ±°λ μ€λ¦μ°¨μμ μ΄λ£¨λ μλ₯Ό μ€λ₯΄λ§ μ λΌκ³ μ μνλ€.
2. μλ 0 μΌλ‘ μμν μ μλ€.
3. μ λ ₯μΌλ‘ μ£Όμ΄μ§λ N μ리 μμμ μ€λ₯΄λ§ μμ κ°―μλ₯Ό μΆλ ₯νλ€.
λμ κ³νλ²(Dynamic Programming) λ°©μμ μ¬μ©νλ€.
π νμ΄ κ³Όμ
N = 1 μΈ κ²½μ° 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 λ‘ μ΄ 10 κ°μ§μ΄λ€.
N = 2 μΈ κ²½μ° 00~09, 11~19, 22~29, .... , 88~89, 99 λ‘ μ΄ 55 κ°μ§μ΄λ€.
μ¬κΈ°μ κ·μΉμ μ°Ύμ보면 2μ리 μ (ab) μμ μΌμ μ리 μ (b) λ μμ μ리 μ (a) μ κ°κ±°λ ν¬λ€λ κ²μ λ°κ²¬ν μ μλ€.
μ¦,, 0b μ κ²½μ° b λ 0λ³΄λ€ ν¬κ±°λ κ°μ κ²½μ°, 1b λ 1λ³΄λ€ ν¬κ±°λ κ°μ κ²½μ°, .... λΌλ κ²μ λ°κ²¬ν μ μλ€.
λ³νλ₯Ό νλ‘ λ³΄λ©΄ λ€μκ³Ό κ°λ€.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
N = 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
N = 2 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
λν 보μ΄λ κ·Έλλ‘ 2μ°¨μ λ°°μ΄λ‘λ νμ΄ κ°λ₯νλ, 1νμ§λ¦¬ λ°°μ΄λ‘ μ²λ¦¬νκ³ μΆμ λ§μμ κ·Έλ κ² μ§λ³΄μλ€.
μ νμμ dp[i] = dp[i] + dp[j] μ΄λ€. ( i κ° 0 μ΄λΌλ©΄ j λ 0~9, i κ° 1 μ΄λΌλ©΄ j λ 1~9 )
μ΄ μ νμμ λ°λΌ N = 3 μ λ€μκ³Ό κ°λ€.
N = 3 | 55 | 45 | 36 | 28 | 21 | 15 | 10 | 6 | 3 | 1 |
λμ§Έ μλ¦¬κ° 0μΈ κ²½μ°, 10 + 9 + 8 + 7 + ... + 1 = 55 κ° λκ³ ,
λμ§Έ μλ¦¬κ° 1μΈ κ²½μ°, 9 + 8 + 7 + ... + 1 = 45 κ° λκ³ ,
λμ§Έ μλ¦¬κ° 2μΈ κ²½μ°, 8 + 7 + 6 + ... + 1 = 36 μ΄ λλ μ΄λ° λ°©μμ΄λ€.
μμ± μΈμ΄: C++
#include <cstdio>
#include <algorithm> // std::fill_n
#define mod 10007
int dp[10] = {0, };
int solve(int num){
int retVal = 0;
// N = 2 μ΄λ©΄ dp λ°°μ΄μ ν λ² λ μ±μμΌνκ³ N = 3 μ΄λ©΄ dp λ°°μ΄μ λ λ² λ μ±μμΌνλ€. -2 ν νμ 루ν
for (int k = 1; k <= num-1; ++k) {
for (int i = 0; i < 10; ++i) {
for (int j = i+1; j < 10; ++j) {
dp[i] = (dp[i] + dp[j]) % mod;
}
}
}
// dp λ°°μ΄μ μ΄ν©μ΄ N μ리 μ€λ₯΄λ§μ κ°μ
for (int i = 0; i < 10; ++i) {
retVal = (retVal + dp[i]) % mod;
}
return retVal;
}
int main(){
int numLeng = 0, count = 0;
std::fill_n(dp, 10, 1);
scanf("%d", &numLeng);
// μ
λ ₯λ°μ N μ리μκΉμ§ κ³μ°ν κ².
count = solve(numLeng);
printf("%d\n", count);
return 0;
}
π λ°°μ΄ μ
λ°λ‘ μμ μ¬μ΄ κ³λ¨ μμ λΉμ·ν λ¬Έμ μ΄λ€.
λ°λ³΅λλ λ¬Έμ λ₯Ό νλ©΄μ ν¨ν΄μ΄ μ‘°κΈμ© κ°μ΄ μ‘νλ λ― νλ€.
λ§μ΄ νμ΄λ³΄λ κ²μ΄ μ€μν μ΄μ κ° μ΄κ²μΈκ°λ³΄λ€.