[백준10844] 쉬운 계단 수 (C++)
#include <iostream>
#include <math.h>
using namespace std;
int mod = 1000000000;
int d[101][10] = { 0 };
int go(int n, int x);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n; cin >> n;
long long sum=0;
for (int i = 0; i < 10; i++)
sum += go(n, i);
cout << sum % mod;
return 0;
}
int go(int n, int x) {
for (int i = 1; i < 10; i++)
d[1][i] = 1;
if (d[n][x])
return d[n][x];
if (x == 9)
d[n][x] = go(n - 1, x - 1) % mod;
else if ((x == 0) && (n != 1))
d[n][x] = go(n - 1, x + 1) % mod;
else if (n!=1)
d[n][x] = (go(n - 1, x + 1) + go(n - 1, x - 1)) % mod;
return d[n][x];
}
길이 N이 주어졌을 때 가능한 계단수(앞 숫자와 연속되는 수)의 개수를 구하는 문제이다. 재귀함수를 이용해 코드를 작성해 보았다.
d[a][b]=c 에서 a는 길이, b는 계단수의 마지막 수, c는 b를 포함한 계단수의 개수를 의미한다.
d[n][x] = (go(n - 1, x + 1) + go(n - 1, x - 1)) % mod;
길이가 n이고 마지막 수 x를 포함한 계단수의 개수를 구하기 위해서 길이가 n-1이고 마지막 수 x+1, x-1인 계단수의 개수를 더한다.
for (int i = 0; i < 10; i++)
sum += go(n, i);
이후 반복문을 이용해 마지막 수를 포함한 계단수의 개수를 모두 더해주면 답을 구할 수 있다.
d[n][x]를 구할 때마다 모듈러 연산을 해서 답의 크기가 너무 커지지 않도록 해준다.
Author And Source
이 문제에 관하여([백준10844] 쉬운 계단 수 (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yoohoo030/백준10844-쉬운-계단-수-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)