[C++] 백준 11057번 오르막 수

 

다이나믹 프로그래밍 문제입니다.

 

줄의 길이가 N개일 때 오르막 수가 가능 한 수들의 경우의 수를 구하는 문제입니다.

오르막 수란 수의 자리가 오름차순을 이루는 것을 말합니다.

인접한 수가 같아도 오름차순입니다.

 

1234, 3346, 2225, 9999가 오름차순의 예입니다.

 

현재 숫자가 앞의 숫자보다 같거나 크면 

앞의 숫자의 경우의 수를 

현재 숫자의 경우의 수에 추가합니다.

 

이를 코드로 보면

for (int i = 1; i <= n; ++i) {
 	for (int j = 0; j < 10; ++j) {
 		if (i == 1) {
 			memo[i][j] = 1;
 		}
 		else {
 			for (int k = 0; k <= j; ++k) {
 				memo[i][j] += memo[i - 1][j - k] % 10007;
 			}
 		}
 	}
}

이렇게 나타낼 수 있습니다.

i는 1~n까지 = 줄의길이에서 현재 위치

j는 0~9까지 차례대로 확인

k는 현재 숫자가 앞의 숫자보다 같거나 클때 값을 대입해주기 위함

 

현재 줄의 위치가 첫번째 줄이면 전부 1을 대입합니다.

다음 위치부터는 현재수보다 이전의 수가 크거나 같으면

이전의 수의 경우의수를 현재값에 더해줍니다.

 

#include <iostream>
using namespace std;

int memo[1010][10];

void init()
{
   for (int i = 0; i < 1010; ++i) {
      for (int j = 0; j < 10; ++j) {
         memo[i][j] = 0;
      }
   }
}

int main(int argc, char *argv[])
{
   init();
   int n;
   cin >> n;

   for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < 10; ++j) {
         if (i == 1) {
            memo[i][j] = 1;
         }
         else {
            for (int k = 0; k <= j; ++k) {
               memo[i][j] += memo[i - 1][j - k] % 10007;
            }
         }
      }
   }
   int max = 0;
   for (int i = 0; i < 10; ++i) {
      max += memo[n][i] % 10007;
   }
   max %= 10007;
   cout << max << endl;

   return 0;
}