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

단계별로 풀어보기 15단계(동적 계획법 1) 9번 문제

https://www.acmicpc.net/step/16

동적 계획법 1 단계

---

백준 10844번: 쉬운 계단 수

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

10844번: 쉬운 계단 수

---

문제 설명

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

---

입력과 출력

입력: 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력: 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

---

접근 방법

이번 문제는 숫자 N을 입력받아 N개 자리인 숫자들 중에서 계산 수가 총 몇개 있는지 구하는 문제다. 계단 수란 45656처럼 모든 숫자가 인접한 자리의 수가 1씩 차이나는 것이다. 단, 0으로 시작해서는 안된다. (ex. 01 같은)

우선 예제 1번의 경우는 1자리 이므로 1, 2, 3, 4, 5, 6, 7, 8, 9로 출력값이 9다. 예제 2번은 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98로 총 17개이므로 출력값이 17이다. 여기서 예제 2번의 답을 보면 앞의 자리 수에 의해 뒷자리 수가 1씩 더하거나 빼서 정해진다. 만약 3자리가 된다면 그 또한 마찬가지로 앞자리에 의해서 뒷자리가 정해질 것이다. 만약 7이 제일 앞자리라면 다음 두자리는 1을 뺀 67 혹은 65가 되거나, 혹은 1을 더해서 87, 89가 될 것이다. 즉, 앞자리 수만 알면 나머지 자리의 경우의 수를 더함으로써 계단 수 갯수를 알 수 있다. 단, 0과 9의 경우에는 뒤에 1과 8만이 올 수 있으므로 따로 구분을 해야한다. 이 점만 주의하면 문제를 해결할 수 있다.

---

코드

#include <stdio.h>
#define div 1000000000

int main(int argc, char *argv[]) {
	int N, sum = 0, arr[101][10];
	scanf("%d", &N);

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

	for (int i = 1; i < 10; i++)
		sum = (sum + arr[N][i]) % div;

	printf("%d\n", sum % div);

	return 0;
}

---

결과

백준 제출 결과