BOJ 10844 쉬운 계단 수

문제출처 : https://www.acmicpc.net/problem/10844

1. 문제요약

- 45656 은 인접한 모든 자리수의 차이가 1 이를 계단수라 함

- n 자리수의 계단수의 갯수는?

- 한자릿수는 9개

2. 접근방법

- 100 자릿수 이므로 브루트 포스는 못함

- dp를 활용

- n-1 자릿수의 마지막 수가 0 이면, n 자릿수의 마지막 수는 -1, 2 인데 -1은 아니므로 2

  n-1 자릿수의 마지막 수가 1~8이면, n 자릿수의 마지막 수는 n-1의 마지막 수 -1, +1

  n-1 자릿수의 마지막 수가 9 이면, n 자릿수의 마지막 수는 8, 0 인데 0은 아니므로 8

- dp에 필요한 항목은 '자릿수', '마지막수'

- d[n][j] : n 자릿수의 마지막 수가 j인 갯수

- 일반적으로 d[n][j] = d[n-1][j-1] + d[n-1][j+1]

3. 시간복잡도

- n

4. 회고

- d[n][j] = d[n-1][j-1] + d[n-1][j+1] 을 j가 0일 때와 9일때로 나누지 않은 이유는

  전역변수로 선언시 d[n][-1] 은 0으로 해주기 때문(음수 인덱스)

- 정답이 1,000,000,000 로 나눈 나머지 이므로 d[n][0] ~ d[n][9] 까지의 합이 int 범위를 넘어 갈 수 있으므로

  ans는 long long으로 선언

- d[101][11]이 아닌 d[101][10] 으로 선언하면 d[n][10] 인경우 인덱스가 넘어가서 다른 값이 나옴

소스코드

#include<iostream>
using namespace std;

int n, d[101][11];
long long ans = 0;

int main(void){
	cin >> n;
	for (int i = 1; i < 10; i++) d[1][i] = 1;
	for (int i = 2; i <= n; i++){
		for (int j = 0; j < 10; j++){
			d[i][j] = (d[i - 1][j - 1] + d[i - 1][j + 1]) % 1000000000;
		}
	}
	for (int i = 0; i < 10; i++) ans += d[n][i];
	cout << ans % 1000000000 << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]