10844 쉬운 계단 수

풀이코드

#include <iostream>
using namespace std;

// 10844
int length;

int cascadingNum(int currentLen, int num){
	// 기저 사례 : 길이가 같아지면 1개
	if(length == currentLen) return 1;
	
	int ret = 0;
	
	switch(num){
		case 0:
			ret += cascadingNum(currentLen + 1, num + 1) % 1000000000;
			break;
		case 9:
			ret += cascadingNum(currentLen + 1, num - 1) % 1000000000;
			break;
		default:
			ret += cascadingNum(currentLen + 1, num - 1) % 1000000000 + cascadingNum(currentLen + 1, num + 1) % 1000000000;
	}
	return ret % 1000000000;
}

int main(){
	int result;
	
	cin >> length;
	
	for(int i = 1; i < 10; i++){
		result += cascadingNum(1, i);
	}
	
	cout << result << endl;
	
}

브루트 포스(무식하게 풀기) 를 적용하여 푼 방법이었습니다. 시간 초과가 나오는 결과를 보였는데, 여기서 깨달은 점은 브루트 포스를 무작정 적용해보기 전에 주먹구구식으로 짐작해보기 를 해보는 것이 중요하다는 것이었습니다. 이 문제에서는 문자의 길이가 100 까지 였으므로 딱 봐도 안된다는 것을 파악하고 점화식을 구하는 방향으로 바로 넘어갔어야 했을 것 입니다.

#include <iostream>
using namespace std;
#define mod 1000000000
// 10844
int length;


int main(){
	int dp[101][10];
	long long result = 0;
	
	cin >> length;
	
	dp[1][0] = 0;
	for(int i = 1; i < 10; i++){
		dp[1][i] = 1;
	}
	
	for(int i = 2; i <= length; i++){
		for(int j = 0; j < 10; j++){
				if(j == 0) dp[i][j] = dp[i - 1][1] % mod;
				else if(j == 9) dp[i][j] = dp[i - 1][8] % mod;
				else dp[i][j] = dp[i - 1][j - 1] % mod + dp[i - 1][j + 1] % mod;
					
			
		}
		
	}
	
	for(int i = 0; i < 10; i++){
		result += dp[length][i];
	}
	
	cout << result % mod << endl;
	
}

해설

끝 자리가 0, 9 로 끝나는 경우에 유의하여서 조건문을 설정해야 합니다. 0 과 9 를 제외한 나머지 숫자들은 그 전 길이의 양 옆 숫자 상황에서의 갯수들을 더해주기만 하면 되며, 0 은 그 전 길이의 1을 그대로 계승. 9 는 그 전 길이의 8을 그대로 계승하면 되겠습니다.

사소한 실수로 여러 번 틀렸었는데, #define 시에 끝에 세미콜론을 붙여서 상수 오타 를 발생시킨 것과 마지막 결과 값에 mod 를 해주지 않아서 틀린 답이 나온 경우 였습니다.