[C++] 백준 10844번: 쉬운 계단 수

문제 바로가기

10844번: 쉬운 계단 수

개요

이 문제는 혼자 골똘히 생각하다가 포기한 문제다.

결국 풀이를 봤는데, 처음에는 이해하지 못 했다.

종이에 여러 번 써보니 이해됐다.

풀이

끝 자리가 0 또는 9일 때는 다음에 붙을 수가 1과 8로 한 가지 밖에 없다.

이외의 수들은 각 2개씩 이어진다.

따라서 각 숫자로 끝나는 수의 개수를 다뤄야 한다.

즉, 단계별 0부터 9까지의 개수를 담는 2차원 배열이 필요하다.

나는 그것을 아래처럼 정의했다.

long long C[100][10]{ {0, 1, 1, 1, 1, 1, 1, 1, 1, 1} };

위 처럼 배열을 정의하면, 값을 지정한 칸을 제외한 남은 칸들은 0으로 초기화 된다.

원래는 memset 함수를 이용했지만 이렇게 하니 편하다.

위에서 지정한 초기값은 N == 1일 때의 값이다. 각각 0부터 9까지의 개수.

점화식은 아래와 같다.

\(C[i][j] = C[i-1][j-1]+C[i-1][j+1]\)

이전 단계의 각 수마다 계단 관계를 갖는 숫자 개수를 늘려주는거다.

예를 들어, i번째 단계의 5는 i - 1번째의 4의 개수와 6의 개수를 합친 것과 같다.

0과 9에 대해서는 out_of_index 오류가 나지 않도록 if문을 이용하여 적절히 처리해준다.

그리고 주의할 점은, \(C[i][j]\)의 값을 정한 이후 1^10의 나머지 연산을 해줘야 한다.

그 뿐만 아니라, 답을 구할 때에도 각 숫자별 개수를 더할 때마다 나머지 연산을 해주지 않으면 문제가 생긴다.

코드

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; i++)
#define INF 987654321
#define EL "\n"

int main() {
	FAST_IO;

	int N;
	cin >> N;

	long long C[100][10]{ {0, 1, 1, 1, 1, 1, 1, 1, 1, 1} };
	for(int i = 1; i < N; i++)
		FOR(j, 10) {
			if (j > 0)
				C[i][j] += C[i - 1][j - 1];
			if (j < 9)
				C[i][j] += C[i - 1][j + 1];
			C[i][j] %= 1000000000;
		}

	int sum = 0;
	FOR(j, 10)
		sum = (sum + C[N - 1][j]) % 1000000000;

	cout << sum << EL;

	return 0;
}