[DP] 백준 문제 풀이 - 10844 쉬운 계단 수

👩🏻‍💻 문제링크

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

✍️ 아이디어

 

1. 문제 이해

• 계단 수가 되려면 인접한 자리의 수가 1 차이여야 함

2. n-1자리수의 수에서 끝자리가 1차이나는 수를 추가하면 n자리수가 됨

->n자리수에서 끝에가 0,1,2,...인 경우를 나눔 (long long result[100001][10];)

 

3. n자리수에서 1은 n-1자리수에서 끝이 0과 2인 수를 더한것과 같다

 

4. n자리수에서 0, 9 는 예외로 처리

 

✍️소스코드

• 내 코드

#include <iostream>	
using namespace std;
long long result[101][10];

int main()
{
	int N; cin>>N;
	long long num=0;
	for(int j=1; j<=9; j++)
	{
		result[1][j]=1;
	}
	for(int i=2; i<=N; i++)
	{
		result[i][0]=result[i-1][1];
		result[i][9]=result[i-1][8];
		for(int j=1; j<=8; j++)
		{
			result[i][j] = (result[i-1][j-1]  + result[i-1][j+1]);
			result[i][j]%=1000000000;
		}
	}
	for(int i=0; i<=9; i++)
	{
		num+=(result[N][i]);
	}
	cout<<num%1000000000<<'\n';
}

 

체감난이도	걸린시간	참고	사용 문법
상	40min	전에 내가 풀었던거	dp인데 케이스 나누는것