[백준][10844번] 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

풀이과정

 

1. dp문제이다.

 

2. N자리수의 값이 K일 경우 N - 1 자리에는 K - 1, K + 1 값이 올 수 있다.

 

dp[N][K] = dp[N][K -1] + dp[N][K +1] 의 식을 구 할 수 있다.

 

3. 0과 9의 경우 -1과 10이 올 수 없으니 조건을 추가해주었다.

 

소스코드

#include<stdio.h>


typedef unsigned long long ull;

ull dp[101][10];

ull solution(int n)
{
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			
			dp[i][j] = 0;
			if (j - 1 >= 0) dp[i][j] += dp[i - 1][j - 1];
			if (j + 1 <= 9) dp[i][j] += dp[i - 1][j + 1];

			dp[i][j] %= 1000000000;
		}
	}

	ull sum = 0;
	for (int j = 0; j <= 9; j++) {
		sum += dp[n][j];
	}
	return (sum % 1000000000);
}

int main()
{
	int n;
	for (int i = 1; i <= 9; i++) {
		dp[1][i] = 1;
	}
	scanf("%d", &n);
	printf("%llu\n", solution(n));
	//1000000000
}