[백준/BOJ] 10844번 쉬운 계단수 (C/C++)

백준 온라인 저지(BOJ) 10844번 쉬운 계단수

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

10844번: 쉬운 계단 수

* 사용언어 : C언어, C++

 

1. 문제

인접한 모든 자리의 차이가 1인 수를 계단 수라고 할 때,

길이가 N인 모든 계단 수의 개수를 출력 (ex. 45656)

 

2. 풀이

전형적인 Dynamic Programming 문제로 메모이제이션 용도로 2차원 dp 배열을 선언했습니다.

2차원 배열 중 첫 번째 차원의 index는 숫자의 자리 수(숫자의 위치)를 의미하고,

두 번째 차원의 index는 각 자리에 들어올 수 있는 숫자를 의미합니다.

 

예를 들어 dp[2][6]에는 두 번째 자리의 숫자가 6일 때의 계단 수가 기록됩니다.

따라서 이 값은 [첫 번째 자리가 5일 때의 계단 수]와 [7일 때의 계단 수]를 더하면 쉽게 만들 수 있습니다.

 

 

가장 실수하기 쉬운 부분만 짚고 넘어가면, 숫자가 0으로 시작하게 되면 계단 수의 길이가 N이 아니게 됩니다.

(문제에서도 0으로 시작하는 수는 계단 수가 아니라고 한 번 더 언급해주었습니다)

 

저는 dp 배열의 1차원 숫자(자리 수)를 일의 자리부터가 아닌 가장 큰 자리 수 부터로 설계했기 때문에

dp[1][0]만을 0으로 초기화하여 문제의 답을 정확하게 맞출 수 있었습니다.

 

참고로 가장 큰 자리 수 외에는 0이 사용될 수 있으므로 설계 시 주의해야 합니다. (ex. 101, 1012, 2101, ...)

 

 

그리고 나머지 연산자(%)는 분배 법칙이 성립합니다.

올바른 답을 출력하기 위해서는 합 연산자가 있는 곳에 모두 나머지 연산자를 넣어주어야 합니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
10844_쉬운 계단 수
1116KB	0ms
*/
#include <cstdio>

const int LM = 101;
const int BASE = 1e9;
int dp[LM][10], N, res;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);

	for (int n = 1; n < 10; ++n) dp[1][n] = 1;
	for (int i = 2; i <= N; ++i) {
		dp[i][0] = dp[i - 1][1];
		dp[i][9] = dp[i - 1][8];
		for (int n = 1; n < 9; ++n) {
			dp[i][n] = (dp[i - 1][n - 1] + dp[i - 1][n + 1]) % BASE;
		}
	}

	for (int n = 0; n < 10; ++n) res = (res + dp[N][n]) % BASE;
	printf("%d\n", res);
	return 0;
}