[알고리즘] 백준 10844번: 쉬운 계단 수 (C++)

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

10844번: 쉬운 계단 수

노트에 구현을 해보았다. 시작 수가 0이면 안 되기 때문에 1 ~ 9까지 수들을 각 수로부터 파생될 수 있는 수들을 트리 형식으로 그려볼 수 있었다.

 

다음과 같은 특징을 지니고 있었다.

1. 시작 수는 0이 될 수 없다.
2. 1 ~ 8까지는 두 가지의 수가 파생될 수 있다.
3. 0과 9는 각각 1, 8 밖에 파생시키지 못한다.

이러한 관계식을 어떻게 나타낼 수 있을까 한참을 고민하다가 2차원 배열을 떠올렸다.

cache[i번째 자리][숫자 j] = 숫자 j가 나온 횟수;

다음 계단식의 특징을 가지고서 점화식을 나타내면

// 맨 처음에는 0을 제외한 수 모두 고를 수 있음
for (int i = 1; i <= 9; i++) {
	cache[1][i] = 1;
}

for (int i = 2; i <= n; i++) {
	for (int j = 0; j <= 9; j++) {
		if (j == 0) {
			cache[i][j] = cache[i - 1][j + 1];
		}
		else if (j == 9) {
			cache[i][j] = cache[i - 1][j - 1];
		}
		else if (j <= 8 && j >= 1) {
        	// 예를 들어 j가 3이면 3은 2나 4로부터 파생될 수 있는 수다.
			cache[i][j] = (cache[i - 1][j - 1] + cache[i - 1][j + 1]) % MOD;
		}
	}
}

(자료형 때문에 오류가 났었다. int 대신 long long으로 잡아주었다.)

---

[AC 코드]

#include <iostream>
using namespace std;
#define MAX 100 + 1
#define MOD 1000000000
#define ll long long

ll cache[MAX][10]; // 10: 0 ~ 9
int n;

int main() {
	cin >> n;

	for (int i = 1; i <= 9; i++) {
		cache[1][i] = 1;
	}

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

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

	sum %= MOD;
	cout << sum;
	return 0;
}

---

이번 문제의 포인트는 '2차원 배열을 떠올릴 수 있느냐 없느냐'인 거 같다. 2차원 배열을 떠올리기 전까지는 노트에 구현을 하면서 '0과 9는 다르다'는 걸 알고만 있었지 1차원 배열로 생각했기에 한 번에 묶어서 고민을 하느라 솔루션이 잘 나오지 않았다.

 

'DP의 2차원 배열' 꼭 기억해야 할 키워드다.