백준 11057번 오르막 수

🔒[문제 url]

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

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <stdio.h> // c
#include <string>
#include <memory.h> // memset
#include <algorithm>
using namespace std;

int n;
long long dp[1001][10];

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
}

void SOLVE()
{
	// 초기 설정
	for (int i = 1; i <= n; i++)
	{
		dp[i][0] = 1; // 0, 00, ~ ,000000000
		dp[i][1] = i;
	}
	for(int i = 0; i < 10; i++) dp[1][i] = 1;


	// Bottom Up Dynamic Programming
	/*
	* dp[x][y] : 길이가 x이고, y로 끝나는 오르막수
	* 
	* dp 설정 조건에 따라,
	* dp[x][0]은 모두 1로, dp[x][1]은 x로 초기화하고,
	* dp[1][x]또한 모두 1로 초기화 할수있다.
	* 
	* dp[x][y]의 값은 끝자리가 y로 고정이므로,
	* dp[x - 1][y] + dp[x - 1][y - 1] + dp[x - 1][y - 2] + ~~~ + dp[x - 1][0]
	* 의 값과 같다. 이를 반복문으로 구현한다.
    *
    * // 수의 범위가 크므로 int가 아닌 long long 선언
	*/
	for (int k = 2; k <= n; k++) // 길이가 k인 오르막수
		for (int i = 2; i < 10; i++) // 끝자리가 i인 오르막수
			for (int j = i; j >= 0; j--) // 에 대해서 dp[k - 1][0 ~ i]를 더한 것이 dp값
			{
				dp[k][i] += dp[k - 1][j] % 10'007;
				dp[k][i] %= 10'007;
			}
	
	long long ans = 0;
	for (int i = 0; i < 10; i++) ans += dp[n][i] % 10'007;
	cout << ans % 10'007;
}

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.