[BOJ] C/C++ 10844 "쉬운 계단 수"

[BOJ] C/C++ 10844 "쉬운 계단 수" 문제풀이

난이도 : SILVER1

---

# 문제

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

---

# 입력

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

---

# 출력

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

 

---

# 소스코드

#include <iostream>
#define mod 1000000000
using namespace std;
int dp[101][10];

int main() {
	int n;
	long long sum = 0;
	cin >> n;
	
	// init
	for (int i = 1;i <= 9;i++) {
		dp[1][i] = 1;
	}

	for (int i = 2; i <= n; i++) {
		for (int j = 0;j <= 9;j++) {
			if (j == 0) dp[i][j] = dp[i - 1][1];
			else if (j == 9) dp[i][j] = dp[i - 1][8];
			else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1])%mod;
		}
	}

	for (int i = 0;i <= 9;i++) {
		sum += dp[n][i];
	}

	cout << sum % mod << endl;

	return 0;
}

---

# 풀이

@ DP(다이나믹 프로그래밍)을 이용한 풀이

BOJ10844 문제는, 끝나는 숫자에 따라, 케이스가 나뉜다.

 

3자리 계단수를 예시로 들어보면

[ㅁㅁ0] 마지막에 오는 숫자가 0인 3자리 계단수를 만들기 위해서는,

2자리 계단수의 마지막 수가 1로 끝나야만 한다.

[ㅁㅁ9] 마지막에 오는 숫자가 9인 3자리 계단수를 만들기 위해서는,

2자리 계단수의 마지막 수가 8로 끝나야만 한다.

[ㅁㅁ1~8] 나머지 1~8 로 끝나는 3자리 계단수는,

2자리 계단수의 마지막 수의 앞뒤에서 올 수 있다.

 

위의 규칙을 점화식으로 만들면 된다.

 

단, 조심할 점은, 문제 조건에서 1000000000 으로 나눈 나머지를 출력하라고 했는데,

이를, 담는 변수인 sum의 자료형을 int로 설정하면 int overflow가 발생해버린다.

따라서 sum의 자료형을 long long 형으로 정의하여, 오버플로우를 방지해야한다.

---

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

- 2020 12 26 problem solving