[C++/Python] 백준 11057 - 오르막 수

문제링크

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

11057번: 오르막 수

 

N이 1일 때는 0~9 까지 10가지 방법이 있습니다.

N이 2이상일 때는 0~9까지 가장 오른쪽 숫자보다 작거나 같은 숫자들의 방법을 모두 더한 값입니다.

예를들어 

N이 3일 때 마지막 숫자가 1이면 001, 011, 111로 3가지가 나오고

마지막 숫자가 2이면 002, 012, 112, 122, 222로 5가지가 나옵니다.

이러한 방법으로 마지막 숫자가 0~9일때 나올 수 있는 모든 방법의 합이 정답이 됩니다.

 

구현 코드

	#include <iostream>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr);
	using namespace std;
	int d[1001][10];
	int main(){
	fastio;
	int n;
	cin >> n;
	for(int j=0;j<10;j++)
	d[1][j] = 1;
	for(int i=2;i<=n;i++){
	for(int j=0;j<10;j++){
	for(int k=0;k<=j;k++){
	d[i][j] += d[i-1][k];
	}
	d[i][j] %= 10007;
	}
	}
	int sum = 0;
	for(int i=0;i<10;i++)
	sum += d[n][i];
	cout << sum % 10007 << endl;
	return 0;
	}

view raw 11057.cpp hosted with ❤ by GitHub

	n = int(input())
	dp = [[0 for i in range(10)] for j in range(1001)]
	for j in range(0,10):
	dp[1][j] = 1
	for i in range(2,n+1):
	for j in range(10):
	for k in range(j+1):
	dp[i][j] += dp[i-1][k]
	dp[i][j] %= 10007
	print(sum(dp[n]) % 10007)

view raw 11057.py hosted with ❤ by GitHub