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

문제 설명

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

11057번: 오르막 수

 

해결 방향

DP문제이다.

백준 10844번(쉬운 계단 수)와 유사하다.

#include<iostream>
using namespace std;
#define mod 10007

int main() {


	int N;
	cin >> N;


	int arr[1001][11];


	for (int i = 0; i < 10; i++)
	{	arr[1][i] = 1;	}


	for (int i = 2; i <= N; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			arr[i][j] = 0;
			for (int k = 0; k <= j; k++)
			{
				arr[i][j] += arr[i - 1][k];
				arr[i][j] %= mod;
			}
		}
	}


	int result=0;
	for (int i = 0; i <= 9; i++)
	{	result += arr[N][i];	}

	cout << result%mod;

}

 

int arr[1001][11];

arr[i][j] = i번째에 숫자j가 있는 경우 오르막 수

 

 

for (int i = 0; i < 10; i++)

{ arr[1][ i ] = 1; }

한자리 일때는 무슨 숫자가 그 자리에 채워져도

한가지 경우의 수 밖에 없으므로

1로 지정해준다.

 

 

for (int i = 2; i <= N; i++)
{
    for (int j = 0; j <= 9; j++)
    {

        arr[i][j] = 0;

        for (int k = 0; k <= j; k++)
        {  arr[i][j] += arr[i - 1][k]; 

           arr[i][j] %= mod;  }

 

    }

}

2자리 이상(N>=2) 일때 결과값을 찾아보자.

 

마지막 자리에 0~9의 숫자가 올 경우 결과값을 구해야하는데

그 결과값은 그 앞자리에 마지막 자리 수보다 작은 수들의 결과값을 모두 합한것과 같다.

 

예를 들어

arr[4][3] = arr[3][3] + arr[3][2] + arr[3][1] + arr[3][0]

따라서

arr[N][n] = arr[N-1][n] + arr[N-1][n-1] + arr[N-1][n-2] + ... + arr[N-1][0]

임을 알 수 있고 다음과 같은 코드를 작성한 것이다.

arr[i][j] = 0;

for (int k = 0; k <= j; k++) {  arr[i][j] += arr[i - 1][k]; }

 

 

int result=0;
for (int i = 0; i <= 9; i++) { result += arr[N][i]; }

결과값을 구하기 위해 N자리의 수에 0부터 9까지 들어갈 경우 나오는 결과값들을 모두 더한다.