[BOJ/10844] 쉬운 계단 수
(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- https://www.acmicpc.net/problem/10844
사용 알고리즘
- DP
풀이
- d[i][j] = i자리 계단수의 개수, i번째 자리의 수는 j
1) 1 <= j <= 8 일 때,
d[i][j] = d[i - 1][j - 1] + d[i - 1][j + 1]
2) j = 0 일 때,
d[i][j] = d[i - 1][j + 1]
3) j = 9 일 때,
d[i][j] = d[i - 1][j - 1]
소스 코드
- https://github.com/moomini/algorithm/blob/master/boj/10844.cpp
|
#include <cstdio>
int d[103][10];
int main(void) { int n; scanf("%d", &n); for (int i = 1; i <= 9; ++i) d[1][i] = 1; for (int i = 2; i <= n; ++i) { for (int j = 0; j <= 9; ++j) { if (j >= 1) d[i][j] += d[i - 1][j - 1]; if (j <= 8) d[i][j] += d[i - 1][j + 1]; d[i][j] %= 1000000000; } } int ans = 0; for (int i = 0; i <= 9; ++i) { ans += d[n][i]; ans %= 1000000000; } printf("%d\n", ans); return 0; } |