[백준 BOJ][DP] 11057 오르막 수

 

 

 

오르막 수는 계단 수와 유사합니다.

그 다음 수를 가기 위한 조건이 있기 때문에 마지막 자리를 저장해줘야 합니다.

 

DP[N][10] 이렇게 선언해주면 0~9의 마지막 숫자를 저장해 줄 수 있습니다.

그리고 0으로 시작할 수 있기 때문에 DP[1][0~9]를 모두 1로 초기화 합니다.

 

마지막 자리가 0이라면

 

 

0~9까지의 숫자가 뒤에 올 수 있습니다.

DP[N][0~9] += DP[N-1][0]

 

마지막 자리가 1이라면

 

 

1~9까지의 숫자가 뒤에 올 수 있습니다.

DP[N][1~9] += DP[N-1][1]

 

.

.

.

 

마지막 자리가 9라면

 

 

9만 뒤에 올 수 있습니다.

DP[N][9] += DP[N-1][9]

 

 

그럼 i는 2부터 n까지, j는 0부터 9까지, k는 j부터 9까지 3중 for문을 돌리면 됩니다.

DP[i][k] += DP[i-1][j] 이런 점화식을 쓸 수 있겠네요.

 

마지막에는 DP[n][0~9]를 다 더해서 출력해 줍니다.

 

10,007로 나눈 나머지로 출력해야하기 때문에 mod 연산을 잘 섞어줍시다.

 

 

코드

 

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

//11057_오르막 수 #include <iostream> #define mod 10007 using namespace std;   int DP[1001][10];   int main(){     int n, sum = 0;     int i, j, k;       cin >> n;       for (i = 0; i <= 9; ++i) DP[1][i] = 1;       for (i = 2; i <= n; ++i){         for (j = 0; j <= 9; ++j){             for (k = j; k <= 9; ++k){                 DP[i][k] += DP[i - 1][j];                 DP[i][k] %= mod;             }         }     }         for (i = 0; i <= 9; ++i) sum += DP[n][i];     cout << sum % mod << endl;          return 0; } Colored by Color Scripter

cs