728x90
https://www.acmicpc.net/problem/10844
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
코드
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>
using namespace std;
int n;
int cache[10][101];
int getStair(int len, int next){
if(len == 1){
return 1;
}
int& ret = cache[next][len];
if(ret != 0){
return ret;
}
if(next+1 <= 9){
ret += getStair(len-1, next+1) % 1000000000;
}
if(next-1 >= 0){
ret += getStair(len-1, next-1)% 1000000000;
}
return ret % 1000000000;
}
int main() {
long long sum = 0;
cin >> n;
memset(cache, 0, sizeof(cache));
for(int i=1; i<10; ++i){
sum += getStair(n, i);
}
cout << sum % 1000000000;
return 0;
}
cache엔 다음 숫자값과 남은 문자열의 길이에 해당하는 계단 수를 저장시켜주었다.
728x90
반응형
'PS > DP' 카테고리의 다른 글
[11053] 가장 긴 증가하는 부분 수열 (0) | 2023.04.16 |
---|---|
[2156] 포도주 시식 (0) | 2023.04.14 |
[1463] 1로 만들기 (0) | 2023.04.13 |
[1932] 정수 삼각형 (0) | 2023.04.13 |
[1149] RGB거리 (0) | 2023.04.11 |