[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 쉬운 계단 수 (10844)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 쉬운 계단 수 (10844)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 쉬운 계단 수 (10844)

 

---

 

10844번: 쉬운 계단 수

[ 문제 ]

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

[ 입력 ]

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

[ 출력 ]

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

---

[ 코드 ]

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

// dp[n][i] : 길이가 n이고, 마지막 숫자가 i인 계단수의 개수
// dp[n][i] = dp[n-1][i-1] + dp[n-1][i+1]

long long dp[101][10];

long long DP(int n,int i) {
	if (n==1)
	{
		if (i==0) // i가 0이면, 0 반환 (0으로 시작하는 수는 없기 때문에)
		{
			dp[n][i] = 0;
			return 0;
		}
		else
		{
			dp[n][i] = 1;
			// 길이가 1이면, 마지막숫자가 무엇이(0이아니면) 나와도 계단수의 개수는 1개
			return 1;
		}
	}
	if (dp[n][i] != -1) // 값이 존재한다면
	{
		return dp[n][i];
	}
	
	if (i==0)
	{
		dp[n][i] = DP(n - 1, 1); // n의 i가 0이면, n-1의 i는 1밖에 올 수 없다.
	}
	else if (i==9)
	{
		dp[n][i] = DP(n - 1, 8); // n의 i가 9이면, n-1의 i는 8밖에 올 수 없다.
	}
	else
	{
		dp[n][i] = (DP(n - 1, i - 1) + DP(n - 1, i + 1)); // 그 외에는
	}
	return dp[n][i]% 1000000000;
	
}

int main() {
	int N; // 1보다 크거나 같고 100보다 작거나 같은 자연수
	cin >> N;

	long long result = 0;

	memset(dp, -1, sizeof(dp));
	// memset(세팅하고자 하는 메모리의 시작주소, 메모리에 시팅하고자 하는 값, 길이)
	// 메모리의 내용(값)을 원하는 크기만큼 특정 값으로 세팅할 수 있는 함수

	for (int i = 0; i <=9 ; i++)
	{
		result = (result + DP(N, i)) % 1000000000;
		// 왜 이게 문제죠..?
	}
	cout << result;

	return 0;

}