백준 10844번- 쉬운 계단 수

문제

45656이란 수를 보자.

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

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

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

입력

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

출력

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

 

#include<iostream>
#include<algorithm>

using namespace std;
unsigned long long arr[101][10];
unsigned long long sum = 0;
int main() {
	int n;
	cin >> n;
	for (int i = 1; i < 10; i++)
		arr[1][i] = 1;
	for (int i = 2; i < n+1; i++) {
		for (int j = 0; j < 10; j++) {
			if (j == 0)
				arr[i][j] += (arr[i - 1][j] + 1) % 1000000000;
			else if (j == 1 || j == 9)
				arr[i][j] += (arr[i - 1][j] * 1) % 1000000000;
			else
				arr[i][j] += (arr[i - 1][j] * 2) % 1000000000;

		}
	}
	for (auto i : arr[n]) {
		sum += i;
		sum %= 1000000000;
	}
	cout << sum % 1000000000 << "\n";
}

[1]-1,2,3,4,5,6,7,8,9
[2]-10,21,12,32,23,43,34,54,45,65,56,76,67,87,78,98,89,

0->1
1->1
2~8->2
9->1

i를 입력받은 n j를 0~9의 수로 생각하고 위의 규칙대로 짜봤는데 틀렸다고한다. 다르게 생각해봐야겠다.

 

 

#include<iostream>
#include<algorithm>

using namespace std;
unsigned long long arr[101][10];
unsigned long long sum = 0;
int main() {
	int n;
	cin >> n;
	for (int i = 1; i < 10; i++)
		arr[1][i] = 1;
	for (int i = 2; i < n+1; i++) {
		for (int j = 0; j < 10; j++) {
			if (j == 0)
				arr[i][j] += (arr[i - 1][1]) % 1000000000;
			else if (j == 9)
				arr[i][j] += (arr[i - 1][8]) % 1000000000;
			else
				arr[i][j] += (arr[i -1][j-1]+ arr[i-1][j+1]) % 1000000000;

		}
	}
	for (auto i : arr[n]) {
		sum += i;
		sum %= 1000000000;
	}
	cout << sum % 1000000000 << "\n";
}

[1]-1,2,3,4,5,6,7,8,9
[2]-10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98
[2]-10,21,12,32,23,43,34,54,45,65,56,76,67,87,78,98,89

 

0은 앞에가 1일때만 붙음
9는 앞에가 8일때만 붙음->
1~8 앞에가 1일땐 2,0 ~8일땐 7 9
을 그대로 구현했더니 풀렸다.