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

11057번 오르막 수

📝문제링크 : www.acmicpc.net/problem/11057

 

이전에 풀었던 쉬운 계단수 문제와 아주 유사하다. 

오르막수가 0으로 끝나려면 0의 앞자리엔 0만 올 수 있다. 

오르막수가 1로 끝나려면 1의 앞자리엔 0과 1이 올 수 있다.

오르막수가 2로 끝나려면 1의 앞자리엔 0과 1과 2가 올 수 있다.

.

.

.

오르막수의 끝자리가 L 인 경우 L의 앞자리엔 0부터 L까지의 수가 올 수 있다.

 

i 는 2부터 N까지, j는 0부터 9까지, k는 0부터 j까지 3중 for문을 돌면 풀 수 있다. 

소스코드

#include <iostream>
using namespace std;

int main()
{
    int	N;
    cin >> N;

    // dp[N][L] : N자리 오르막수에 대해, 끝자리가 L인 수의 개수
    int dp[1001][10];

    //set initial value
    for(int i = 0; i < 10; i++)
        dp[1][i] = 1;		

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

    int sum = 0;
    for(int j = 0; j < 10; j++)
	    sum = (sum + dp[N][j]) % 10007;	
    cout << sum << '\n';
    return (0);
}

 

---

 

c++ 문법 new랑 delete 이용해서 이 코드 다시 짜보기

 

2차원 배열 메모리 할당 및 해제 방법

 

👇 new로 할당

int sizeX = 5;
int sizeY = 10;
 
int **arr = new int*[sizeY];
 
for (int i = 0; i < Y; i++)
    arr[i] = new int[sizeX];

 

 

👇 delete로 해제

for(i = 0; i < sizeY; i++)
    delete[] arr[i];
delete arr[];

 

#include <iostream>
using namespace std;

int main()
{
	int	N;
	cin >> N;

	//dynamic allocation of memory
	int	**dp = new int*[N + 1];

	for (int i = 0; i < N + 1; i++)
		dp[i] = new int[10];
	
	//set initial value
	for(int i = 0; i < 10; i++)
		dp[1][i] = 1;		

	for(int i = 2; i <= N; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			dp[i][j] = 0;
			for (int k = 0; k <= j; k++)
			{
				dp[i][j] = (dp[i][j] + dp[i - 1][k]) % 10007;
			}
		}
	}
	
	int sum = 0;
	for(int j = 0; j < 10; j++)
		sum = (sum + dp[N][j]) % 10007;	
	cout << sum << '\n';
	
    //delete
	for(int i = 0; i < (N + 1); i++)
		delete[] dp[i];
	delete[] dp;

	return (0);
}

 

 

---

• 백준 2193번 이친수 문제도 이 유형과 아주 유사하다. 이친수 문제는 포스팅 생략.