BOJ (C/C++) 10844번: 쉬운 계단 수

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

10844번: 쉬운 계단 수

---

풀이

길이가 N-1인 계단수의 끝자리 숫자에 따라 길이가 N인 계단수의 개수가 정해진다.

길이가 N-1인 계단 수의

끝자리가 0 (ex. 10, 210...) : N자리인 계단 수는 101, 2101로 1개씩만 존재

끝자리가 9 (ex. 89, 6789...) : N자리인 계단 수는 898, 67898로 1개씩만 존재

끝자리가 1~8 (ex. 21, 8...) : N자리인 계단 수는 210, 212, 87, 89로 각각 2개씩 존재

 

따라서 DP 배열을 DP[길이][끝 숫자] 로 설정했다.

- 길이가 1인 계단 수는 1,2,...9로 각 자리당 1개씩 존재

- 길이가 2 이상인 계단 수

  끝자리가 0, 9일 땐 DP[N-1][0], DP[N-1][8] 개

  끝자리가 1~8일 땐 DP[N-1][끝자리-1] + DP[N-1][끝자리+1] 개이다

---

코드

#include <stdio.h>

#define DIV 1000000000

int main() {
	int N, sum = 0;
	int DP[101][10] = { 0, };

	scanf("%d", &N);

	// 1의 자리수
	for (int i = 1; i < 10; i++) DP[1][i] = 1;

	// 길이가 2 ~ N인 계단 수
	for (int i = 2; i <= N; i++) {
		DP[i][0] = DP[i - 1][1];
		DP[i][9] = DP[i - 1][8];

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

	// 길이가 N인 계단 수
	for (int i = 0; i < 10; i++) {
		sum = (sum + DP[N][i]) % DIV;
	}

	printf("%d", sum);

	return 0;
}