[Baekjoon] 11057번: 오르막 수 / dynamic
https://www.acmicpc.net/problem/11057
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수
www.acmicpc.net
오르막수는 인접한수가 같아도 오름차순으로 치고, 0부터 시작 가능하므로,
수의 길이가 1일때, 자기 자신 수 0,1,2,3,4,5,6,7,8,9로 10개,
수의 길이가 2일때,
00, 01, 02, 03, 04, 05, 06, 07, 08, 09 -> 10개 11, 12, 13, 14, 15, 16, 17, 18, 19 -> 9개 ...
99 -> 1개
다 더하면 1+2+3+4+5+6+7+8+9+10으로 55개이다.
수의 길이가 3일때는, 000, 001, 002, 003, 004, 005, 006, 007, 008, 009 -> 10개 011, 012, 013, 014, 015, 016, 017, 018, 019 -> 9개 ... 099 -> 1개 : 여기까지 55개 111, 112, 113, 114, 115, 116, 117, 118, 119 -> 9개 ... 199 -> 1개 : 여기까지 45개 즉, 1+3+6+10+15+21+28+36+45+55 (수의 길이가2일때의 누적 합) = 220이다.
마찬가지로 수의길이가 4일때는 수의길이가 3일때의 누적 합 1+4+10+10+20+35+56+84+120+165+220 = 715
수의길이가 n일때 오르막수는 수의길이 n-1일때 누적 합을 구하면 된다.
코드
//11057
#include <iostream>
#include <cmath>
using namespace std;
int main(int argc, const char * argv[]) {
cin.tie(NULL);
ios::sync_with_stdio(0);
int N;
long long up[1010][11];
for(int i=1;i<=10;i++) up[1][i] = i;
cin >> N;
for(int i=2;i<=1001;i++){
for(int j=1;j<=10;j++){
up[i][j] = (up[i][j-1] + up[i-1][j])%10007;
}
}
cout << (up[N][10])%10007;
return 0;
}