[210520][백준/BOJ] 10844번 쉬운 계단 수
문제
입출력
풀이
계단수란 인접한 모든 자리수의 차이가 1이 나는 수를 말한다.
45656는 모든 인접한 자리수가 1씩 차이가 난다. 따라서 이는 계단수이다.
n이 1일때는 1, 2, 3, 4, ... 9까지 총 개의 계단수가 있다. 문제에서 0으로 시작하는 수는 없다고 명시하였으므로 총 9개가 존재한다.
n이 2일때는 10, 12, 21, 23, ... 87, 89, 98까지 총 17개의 계단이 존재한다.
이러한 규칙을 이용해서 점화식을 만들어보면
d[n][L] = d[n-1][L-1] + d[n-1][L+1]
길이가 n, L은 숫자
임을 알 수 있다.
위 점화식은 L이 1부터 8까지 일때만 유효한 점화식이다.
0은 +1만 할 수 있으며 9는 -1만 할 수 있기 때문이다.
따라서 위 예외까지 합친 점화식은 다음과 같다
L이 0일때 d[n][L] = d[n-1][L+1]
L이 9일때 d[n][L] = d[n-1][L-1]
L이 1부터 8까지일때 d[n][L] = d[n-1][L-1] + d[n-1][L+1]
코드
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000000
int d[102][102];
int dp(int n)
{
for (int i = 0; i < 9; ++i)
d[1][i] = 1;
for (int i = 2; i <= n; ++i)
{
for (int j = 0; j <= 9; ++j)
{
if (j == 0) d[i][j] = d[i - 1][j + 1] % MOD;
else if (j == 9) d[i][j] = d[i - 1][j - 1] % MOD;
else d[i][j] = (d[i - 1][j - 1] + d[i - 1][j + 1]) % MOD;
}
}
int sum = 0;
for (int i = 0; i < 10; ++i)
sum = (sum + d[n][i]) % MOD;
return sum;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
cout << dp(n);
}
Author And Source
이 문제에 관하여([210520][백준/BOJ] 10844번 쉬운 계단 수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kwkim95/210520백준BOJ-10844번-쉬운-계단-수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)