https://www.acmicpc.net/problem/11057
11057번: 오르막 수오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수www.acmicpc.net
10884 쉬운 계단수에서 한단계 진화한 문제다.
2차원 배열을 생성하여 풀었다.
dp[i][j]는 길이가 i인 끝자리가 j로 끝나는 오르막 수의 개수를 의미한다.
첫번째는 0이니깐 비워놓고,
모든 한자리수는 오르막수이기 때문에 dp[1][0~9] 는 모두 1이다.
2자리수부터가 문제인데,
dp[2][0]은 00 하나밖에 존재할 수 없다.
dp[2][1]은 01,11 2개가 존재할 수 있고,
dp[2][2]는 02,12,22 3개가 존재 할 수 있다.
3자리수부터는
dp[3][0]=1 (000)
dp[3][1]=3 (001,011,111)
dp[3][2]=6 이다(002,012,112,022,122,222)
즉 이를 직관적으로 이해해보면,
i자리의 끝이 j로 끝나는 수는, i-1자리의 0,1, 2, 3 …… j 로 끝나는 수들의 합이 된다.
이를 점화식으로 세워보면
**dp[i][j]= sum(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]….**dp[i-1][j-1]+dp[i-1][j])가 된다는 것을 알 수 있다.
%%
여기서 한 단계만 더 나아간다면,
dp[i][j-1] 즉, i자리를 가진 끝이 j-1로 끝나는, dp[i][j]의 왼쪽에 있는 수는
위에있는 점화식을 통하여
dp[i][j-1]= sum(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]….dp[i-1][j-1]) 임을 알 수 있다.
**그러므로:**dp[i][j]= sum(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]….dp[i-1][j-1]+dp[i-1][j])
에서 sum(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]….dp[i-1][j-1]) 까지를 dp[i][j-1]로 치환하면
dp[i-1][j]만 남으므로
dp[i][j] = dp[i-1][j]+dp[i][j-1]임을 알 수 있다.
n=int(input())dp=[[0]*10 for _ in range(n+1)]dp[1]=[1]*10for i in range(2,n+1):
for j in range(0,10): if j==0: dp[i][j]=1
continue dp[i][j]=dp[i-1][j]+dp[i][j-1]
print(sum(dp[n])%10007)