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

1. 문제

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

10844번: 쉬운 계단 수

 

 

2. 풀이

DP적 접근

문제를 읽고 세번째까지는 구조도를 그려봤습니다. 구조를 보면 결국 완전탐색을 통해 모든 경우의 수를 찾는 문제입니다.

그런데 다음 자리로 늘어나는 과정에서 완전탐색의 시간복잡도는 O(2ⁿ)이 됩니다. 

따라서 DP나 그리디를 써야 하는데 아까 그린 구조도를 살펴보면 두 가지 특징을 가집니다.

• 반복되는 부분문제(Overlapping Subproblems)
  다음 자리로 늘어나는 과정에서 같은 부분문제들이 반복됩니다.
• 최적 부분구조(Optimal Substructur)
  위의 부분문제들은 다른 부분문제를 해결하는데 영향을 미치지 않습니다. 예를 들어 3을 만드는 경우는 2→ 3, 4→ 3입니다. 하지만 이 부분문제는 5를 결정하는데 영향을 주지 않습니다.

이 두 규칙을 발견했다면 부분문제를 정의할 수 있습니다. 

부분문제 정의

우리가 해결해야할 부분문제는 i번째 자리에 k가 오는 경우의 수를 구하는 것입니다. 여기서 부분문제를 해결하는데 중요한 정보는 i-1번째 마지막에  k가 오는 경우입니다. 따라서 자리수와 마지막에 오는 수 두 정보로 규칙을 찾을 수 있습니다.

규칙성을 발견하면 다음과 같은 점화식을 세울 수 있습니다. d(i, j)를 i번째 자리에 j가 오는 경우의 수라고 합시다.

if j = 9, d(i, j) = d(i - 1, j - 1)
if j = 0, d(i, j) = d(i - 1, j + 1)
else, d(i, j) = d(i - 1, j - 1) + d(i - 1, j + 1)
단, d(1, 0) = 0, d(1, j) = 1 (j = 1, 2, ..., 9)

일반적으로 같은 규칙을 같지만 마지막 수가 0 또는 9일 때에는 다른 규칙을 갖습니다. 따라서 이를 고려하여 예외처리를 해주었습니다. 이를 바탕으로 Tablation 하면 아래의 테이블을 채울 수 있습니다.

i \ j	0	1	2	3	4	5	6	7	8	9	sum
1	0	1	1	1	1	1	1	1	1	1	9
2	1	1	2	2	2	2	2	2	2	1	17
3	1	3	3	4	4	4	4	4	4	3	34
4	3	4	7	7	8	8	8	8	7	4	64
5	4	10	11	15	15	16	16	15	12	7	121

 

3. 구현코드

#include<iostream>
#define MOD 1000000000
typedef long long LL;

using namespace std;

LL N, ans;
LL d[101][10];

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	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++) {
			if (j == 0) d[i][j] = d[i - 1][j + 1];
			else if (j == 9) d[i][j] = d[i - 1][j - 1];
			else d[i][j] = d[i - 1][j - 1] % MOD  + d[i - 1][j + 1] % MOD;
		}
	}
	
	for (int i = 0; i < 10; i++) ans += d[N][i];
	cout << ans % MOD;
}

구현시 주의할 점은 수가 커질 수 있으므로 long long을 써주는 것과 dp테이블에서 첫 번째 수를 미리 초기화해주는 것입니다. 이 부분만 주의하면 잘 풀수 있습니다.