백준 10844 쉬운 계단 수

아니 왜 이 스킨은 글쓰기 버튼이 없는거지

내가 못찾나

아 깔끔해서 다 좋은데 글쓰기 버튼이 없어 왜ㅠㅠ 힝

어쨋든...... 쉬운 계단 수 문제이다

쉬운....

쉽지 않았다

이전 숫자에 대해 그 다음 숫자가 적절하게 오는 경우의 수만 계산 하면 돼겠다! 라고 생각하고 

햐! 쉽네!

라고 생각했는데

0 이라는 복병이..

그래서 이전 자리에 오는 수가 무엇이냐에 따라 다르게 생각했다

이전 자리가 0이면 다음 자리에 1이 오고

이전 자리가 1이면 다음 자리에 0이나 2가 오고

이전 자리가 2이면 다음 자리에 1이나 3이 오고

.

.

.

.

이전 자리가 8이면 다음 자리에 7이나 9가 오고

이전 자리가 9이면 다음 자리에 8이 온다

점화식을 써보면

DP(0, len) = DP(1, len -1)

DP(1, len) = DP(0, len - 1) + DP(2, len-1)

.

.

.

이렇게...

메모이제이션을 적용한 memo[i][j]는 '이전 자리의 숫자가 i일 경우 j길이의 계단수의 개수' 를 뜻한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int memo[10][101];

int result(int n) {
	int res = 0;
	for (int i = 0; i < 9; i++) {
		res = (res + memo[i][n]) % 1000000000;
	}
	return res;
}
int main() {
	int n;
	cin >> n;
	memo[0][0] = 0;
	for (int i = 0; i < 10; i++) {
		memo[i][0] = 1;
	}

	
	for (int i = 1; i < n; i++) {
		memo[0][i] = memo[1][i - 1] % 1000000000;
		for (int j = 1; j <= 8; j++) {
			memo[j][i] = (memo[j - 1][i - 1] + memo[j + 1][i - 1]) % 1000000000;
		}
		memo[9][i] = (memo[8][i - 1]) % 1000000000;
	}
	int res = result(n-1);
	
	cout << res << endl;
}

신기하게 한방에 맞았다.

memo[1]~memo[8]을 합쳐서 최적화 할 수 있을거 같지만

다음 문제가 빨리 보고 싶어서 안했다

ㅎㅎ 흔한 멍청이식 문제 풀이 ㅎㅎ 고딩때도 응용문제 안풀고 그랬는데 ㅎㅎ