BOJ 10844 (쉬운 계단 수)

• 문제
  45656이란 수를 보자.
  
  이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
  
  N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.
  
  
• 입력
  첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
  
  
• 출력
  첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

#include<iostream>
#include<cmath>
#define MOD 1000000000
using namespace std;
int N;
long long dp[101][10];
long long answer;
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

void fillDp()
{
	for (int i = 2; i < 101; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			if (j == 0) {
				dp[i][j] = dp[i - 1][j + 1] % MOD;
			}
			else if (j == 9) {
				dp[i][j] = dp[i - 1][j - 1] % MOD;
			}
			else {
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
			}
		}
	}
}

int main()
{
	fast_io();
	// 끝이 0이거나 9이면 1개만 추가된다 (1,8 밖에 올 수 없음)
	cin >> N;
	for (int i = 1; i < 10; i++)
	{
		dp[1][i] = 1;
	}
	fillDp();
	for (int i = 0; i < 10; i++)
	{
		answer += dp[N][i];
	}
	cout << answer%MOD;
	return 0;
}

   이전 길이의 숫자 결과를 이용해서 자릿 수가 추가 될 때 끝자리를 기준으로 다음 길이의 끝자리 수의 숫자를 누적해 나가면 된다
(DP를 사용하면 되는데 바로 캐치하지 못하고 수식을 만드려고 했지만 실패했다)

끝자리가 0, 9인 경우는 이전 길이에서 끝자리가 1, 8일때만 가능하므로 조건을 따로 빼주고 나머지 끝자리 수는 이전 자리에서 해당 끝자리의 앞 뒤 숫자의 갯수 만큼 더해주면 된다.

또 자릿수가 100자리면 int형 및 long long 형으로도 부족하기 때문에 10억으로 나누어 출력하라고 한 것 같다.
(DP 배열을 채우는 과정에서 10억을 나눈 수를 넣었지만 결과를 출력하기 위해 0~9 까지 더할 때 다시 오버플로우가 발생할 수 있으므로 또 10억을 나누어 주는 작업이 반드시 필요하다)

시간 복잡도 : O(N^2)

숏코딩 1 -> 2차원 배열을 쓰지 않은 풀이 (이해가 잘 안된다..)

#include<stdio.h>
#define M 1000000000
int n, k, i, d[10];

int main(){
	for(i=1; i<=9; i++) d[i]=1;
	scanf("%d", &n);
	while(--n){
		int t[10]={};
		t[1]+=d[0]; t[8]+=d[9];
		for(i=1; i<9; i++){
			t[i-1]=(t[i-1]+d[i])%M;
			t[i+1]=(t[i+1]+d[i])%M;
		}
		for(i=0; i<=9; i++) d[i]=t[i];
	}
	for(i=0; i<=9; i++) k=(k+d[i])%M;
	printf("%d", k); 
}

숏코딩 2 -> 0,9 를 위한 여유 공간 마련?

#include <iostream>
using namespace std;

int M = 1000000000, I, J, N, A;
int D[100][12]{ 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 };

int main()
{
	cin >> N;
	for (I = 1; I < N; I++)
		for (J = 1; J <= 10; J++)
			D[I][J] = (D[I - 1][J - 1] + D[I - 1][J + 1]) % M;

	for (I = 1, J = 0; I <= 10; I++) J = (J + D[N - 1][I]) % M;
	cout << J;
	return 0;
}