[BAEKJOON] 10844번 쉬운 계단 수

문 제

 

소 스  코 드

#include<iostream>

constexpr int MAX	{ 1'000'000'000 };

int main() {

	int N;
	std::cin >> N;

	int **temp = new int*[N];
	for (int i = 0; i < N; ++i) temp[i] = new int[10];
	
	temp[0][0] = 0;
	for (int i = 1; i < 10; ++i) temp[0][i] = 1;

	for (int i = 1; i < N; ++i) {
		temp[i][0] = temp[i - 1][1];
		temp[i][9] = temp[i - 1][8];

		for (int j = 1; j < 9; ++j) {
			temp[i][j] = (temp[i - 1][j - 1] + temp[i - 1][j + 1]) % MAX;
		}
	}


	int max_num{ 0 };
	for (int i = 0; i < 10; ++i) max_num = (max_num + temp[N - 1][i]) % MAX;

	std::cout << max_num;
	

	for (int i = 0; i < N; ++i) delete[] temp[i];
	delete[] temp;

	return 0;
}

 

풀 이

 

• 규칙 찾기
  N : 1인 경우 1 2 3 4 5 6 7 8 9 이고,
  N : 2일 경우 1과 9를 제외한 나머지 값은 +1, -1 두가지가 가능하다.
  N[2][0] = N[1][1], N[2][9] = N[1][8] 을 제외 하고는 모두 2개 씩 가진다.
  N : 3일 경우 앞에 누적된 값에 앞의 사항을 반복한다.

 

 

결 과 값

 

 

문 제  출 처

문제 링크 : [ BAEKJOON ] : https://www.acmicpc.net/problem/10844