쉬운 계단 수 (feat. 백준, 10844번)

쉬운 계단 수
https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/10844
#include <iostream>
#include <numeric>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N;
	register long long arr[101][10] = { 0 };
	for (register int i = 1; i <= 9; ++i)
		arr[1][i] = 1;
	cin >> N;
	for (register int i = 2, j; i <= N; ++i)
		for (j = 0; j < 10; ++j) {
			if (j == 0)
				arr[i][0] += arr[i - 1][1];
			else if (j == 9)
				arr[i][9] += arr[i - 1][8];
			else
				arr[i][j] += arr[i - 1][j - 1] + arr[i - 1][j + 1];
			arr[i][j] %= 1000000000;
		}
	cout << accumulate(arr[N], arr[N] + 10, 0ll) % 1000000000 << endl;
	return 0;
}
// *&)*@*

1. 쉽지 않은 계단 수입니다.
2. 백준에서 dp문제를 순서대로 풀었을때, 이번 문제가 가장 dp다운 문제라고 생각합니다.
3. 풀이를 적다보니 제가 꼬여서 더 쉽게 해설을 해둔 다른분의 블로그를 링크합니다.

백준 10844번 쉬운 계단 수 :: 마이구미