< 백준 BaekJoon : 10844번 쉬운 계단 수 > C++

<< 문제 >>

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

10844번: 쉬운 계단 수

 

좀 애를 먹었던 문제

 

나는 1~9로 시작하는 수로 숫자를 세어보려 했는데,

 

0~9로 끝나는 숫자의 수를 저장하고 다음 턴에서 뭐  3으로 끝나는 수를 구하고 싶으면 

 

1. 4에서 끝나는 수 뒤에 3 붙이기

2. 2에서 끝나는 수 뒤에 3 붙이기

 

그래서 [i][3] = [i-1][2] + [i-1][4] 이런 식으로 점화식을 구성해야 한다. 

 

 

<< 코드 >>

#include <iostream>
using namespace std;

long long arr[100][10];

int main() {

	int num;
	cin >> num;

	arr[0][0] = 0;
	for (int i = 1; i < 10; i++) {
		arr[0][i] = 1;
	}

	for (int i = 1; i < num; i++) {
		for (int j = 0; j < 10; j++) {
			
			if (j == 0) {
				arr[i][j] = arr[i - 1][1];
			}
			else if (j == 9) {
				arr[i][j] = arr[i - 1][8];
			}
			else {
				arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j + 1];
			}

			arr[i][j] %= 1000000000;
		}
	}
	long long sum = 0;
	for (int i = 0; i < 10; i++) {
		sum += arr[num - 1][i];
		sum %= 1000000000;
	}

	cout << sum;
}

 

 

 

<< 깃헙 >>

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/10844.%E2%80%85%EC%89%AC%EC%9A%B4%E2%80%85%EA%B3%84%EB%8B%A8%E2%80%85%EC%88%98