백준 11057번 _ 오르막 수

2020-05-09 · 배운 것 · 2분 읽기

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

11057번: 오르막 수

풀이방법

dp문제이며 직전에 푼 쉬운 오르막과 거의 유사한 문제다. 그냥 똑같다고 보면됨. 그러므로 생략하겠습니다.ㅎ

전체코드

#include <iostream>
#include <algorithm>

#define DIV_NUM 10007

using namespace std;
long long dp[10][1001];
int N;

void dpInit()
{
	for (int i = 0; i <= 9; i++)
		for (int j = 0; j <= N; j++)
			dp[i][j] = -1;
}

long long getCount(int number, int n)
{
	long long& ret = dp[number][n];
	if (ret != -1) return ret;

	if (n == N)
		return 1;

	ret = 0;
	for (int i = number; i <= 9; i++)
		ret = (ret + getCount(i, n + 1)%DIV_NUM);
	return ret%= DIV_NUM;
}

void solve()
{
	long long cnt = 0;
	for (int i = 0; i <= 9; i++)
		cnt = (cnt + getCount(i, 1))%DIV_NUM;
	cout << cnt;
}

int main()
{
	cin >> N;
	dpInit();
	solve();
	return 0;
}

후기