[BOJ/C++]11057번 오르막 수

https://www.acmicpc.net/problem/11057

11057번: 오르막 수

---

문제

'2234', '3678', '11119'와 같이 인접한 수가 같거나 오름차순인 수를 "오르막 수"라고 한다.

n길이의 오르막 수 개수를 구해라.

 

풀이방법

https://lionontheshore.tistory.com/33?category=929275

[BOJ/C++]10844 번 쉬운 계단 수

와 같은 방식으로 풀었다.

다만, 오르막 수의 경우는 [i][j]에서 j보다 작은 모든 수를 더해야 하기 때문에

먼저 dp[i][0]=dp[i-1][0]으로 정의해주고(0은 뒤에 0밖에 갖기 못하기 때문에)

 dp[i][j]=dp[i][j-1]+dp[i-1][j-1]로 점화식을 구해주었다.

예를 들면 j=1인 경우에

 dp[i][1]=dp[i][0]+dp[i-1][1]=dp[i-1][0]+dp[i-1][1]이고,

j=2

 dp[i][2]=dp[i][1]+dp[i-1][2]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]

와 같이 j아래 모든 수를 더해줄 수 있다.

 

 

소스코드

#include<iostream>
using namespace std;

int main(void){
    int n;cin>>n;
    int dp[n+1][10];

    for(int i=0;i<10;i++)
        dp[1][i]=1;
    
    for(int i=2;i<=n;i++){
        dp[i][0]=dp[i-1][0];
        for(int j=1;j<10;j++)
            dp[i][j]=(dp[i][j-1]+dp[i-1][j])%10007;
    }

    int sum=0;
    for(int i=0;i<10;i++)
        sum=(sum+dp[n][i])%10007;
    cout<<sum<<endl;
}