10844 완전 어려운 계단 수

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string>
using namespace std;
int dp[101][11]; //i자리 숫자면서 j로 시작하는 계단 수 -> 틀림
//이거 남들은 j로 끝나면~으로 하던데 시작해도 딱 떨어지는 것 같음(아마..일단 내가 계산한 만큼은) -> 이거 틀림
//다만 10으로 시작하는 건 1개씩 늘어나고 12로 시작하는 건 2개씩 늘어나니까 [1][0]은 10~, [1][1]은 12~로 나눠줌 ->틀림
//----------
//i자리 숫자면서 j로 끝나는 계단 수로 해야 계산이 됨ㅋㅋ
int main() {
	int x;
	cin >> x;
	if (x == 1) cout << 9;
	else {
		dp[1][0] = 0; //10으로 시작하는 수는 1, 10, 101, 1010 이렇게 올라감
		for (int i = 1; i <= 8; i++) dp[1][i] = 1;
		dp[1][9] = 1;
		for (int i = 2; i <= x; i++) {
			//dp[i][0] = 1; //1, 10, 101, 1010... 모든 i에서 1개씩밖에 없다(10으로 시작하는 수는 1개씩이라고 생각한다)
			dp[i][0] = dp[i - 1][1];
			for (int j = 1; j <= 8; j++) { //나머지 수는 한 자리수 커질 때마다 작고/크고 2개씩 나온다
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
			}
			//if (i == 2) dp[i][9] = 1;
			//else dp[i][9] = dp[i - 1][9] + 1; //9, 98, 987/989, 9876/9878/9898, ... 이렇게 늘어난다. 1, 1, 2, 3..이니까 i=2일 때도 1이어야 해서 따로 처리
			dp[i][9] = dp[i - 1][8];

			//주석 부분은 (j로 시작하는 계단 수) 틀린 코드 부분
			//i짜리 자리수면서 j로 끝나야 함
		}
		long long sum = 0;
		for (int i = 0; i <= 9; i++) {
			//cout << dp[x][i] << endl;
			sum += dp[x][i];
		}
		cout << sum % 1000000000;
	}
}

dp문제 뒤에서부터 계산하는 거 직관적이지 않아서 머릿속에 잘 안 그려진다

앞에서부터 계산하는 방법이 있을까 해서 삽질했지만 경우의 수가 좀 많이 나눠진다 그래서 다 처리했다고 생각했도 어딘가 터진다;

123더하기 문제에서 했던 것처럼 뒤에서부터 한 자리씩 확정하는 게 좋다 검증된 풀이의 이유가 다 있는 듯 하다..