[백준] 알고리즘 10844번 - 쉬운 계단 수 문제

문제

소스코드

#include <bits/stdc++.h>
using namespace std;
int dp[101][10];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 1; i <= 9; i++)dp[1][i] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j == 0) dp[i][j] = dp[i - 1][j + 1];
			else if (j == 9) dp[i][j] = dp[i - 1][j - 1];
			else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
			dp[i][j] %= 1000000000;
		}
	}
	int ans = 0;
	for (int i = 0; i < 10; i++) {
		ans += dp[n][i];
		ans %= 1000000000;
	}
	
	cout << ans;
}

풀이

dp에는 자릿수 , 끝에오는 수에 따라 오는 경우의 수 이렇게 2차원 배열을 이용하여 저장하면 된다.

끝자리에 오는 숫자가 0이거나 9일 경우는 하나의 숫자들 밖에 올 수 없으니 이건 조건문을 걸어준다.

마지막으로 mod처리를 둘다 해줘야 결과가 틀렸다고 안나온다.. 이것때문에 몇번 틀렷다.