#include <bits/stdc++.h>
using namespace std;
long long memo[10][100] {};
long long stairNumber(int n , int digit)
{
if(digit<=1)
{
return 1;
}
if(memo[n][digit])
{
return memo[n][digit]% 1000000000;
}
else
{
if(n-1 >= 0)
{
memo[n][digit] += stairNumber(n-1,digit-1) % 1000000000;
}
if(n+1 <= 9)
{
memo[n][digit] += stairNumber(n+1, digit-1) % 1000000000;
}
}
return memo[n][digit] % 1000000000;
}
int main(void)
{
int N = 0;
cin>>N;
long long result = 0;
for(int i =1; i<10; i++)
{
result += stairNumber(i, N);
result %= 1000000000;
}
cout<<result<<'\n';
}
우선 완전탐색으로 계단 수를 구하는 아이디어 자체는 별로 어렵지않았다.
한 차례 차례 자릿수를 내려가며 계단 수가 있는지 조사했다.
그리고 어떤 값들을 저장해서 다시 활용해야할지 생각해보니
결국 각 자릿 수가 자신의 아래로 가지는 계단 수는 정해져있더라.
그래서 재귀적으로 각 자릿수에 따른 0부터 9까지의 값이 가질 수 있는 계단수를 구해줬다.
10억으로 나눈 나머지를 저장하게 하는데서 실수를 했다.
계단 수를 구하는 과정에서 모든 연산에 mod 연산을 해줬기에..
각 값들은 모두 10억보다 낮은 값이지만,
마지막 result를 구하는 과정에서 각 값들의 합이 10억을 초과해버렸다.
(사실 mod 연산을 다 해줄 필요는 없었을 것 같기도하다;
48, 52번째 줄만 해줘도 됐을 듯? 아닌가?)
마지막까지 긴장의 끈을 놓지 않아야한다...
.. 참깨라면 다 끓여놓고 다 먹은 다음 유성스프를 발견한 기분이랄까?
제출하기 전에 한번 더 검토하자.
내 머릿속의 검토 알고리즘을 정해놔야겠다.
그리고 반례를 찾는 과정에서 자동 입력 테스터기를 하나 만들어봐야겠다는 생각을 했다.
https://ideone.com/n9K9id 이런 것 처럼?
한번쯤 시간을 내보자.
