백준 10844

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

10844번: 쉬운 계단 수

이건 개념은 쉬웠다 근데 계속 틀렸습니다 나오길 래 코드를 뜯어봤더니 int의 범위를 초과해서 갑자기 값이 음수로 바뀌는 사태가 발생해서 100정도를 넣으면 값이 이상하게 나왔다 그래서 이코드는 중간중간에 값에다가 모듈러 연산을 해서 저장해주는 게 해결책이었다.

자 일단 첫번째 자리수 즉 수의 맨앞에 나오는 수는 0이 나오면 안된다 그렇기에 첫번째 자릿수가 0

이 될 경우의 수 는 0이다 그리고 나머지는 첫번째 자리에 나오는게 가능하니 1이다

2번째자릿수의 0은 이전자리에서 1에서 오는 방법밖에 없다 9도 마찬가지다 9로가는 방법은

이전자리의 수에서 8에서 밖에 오는 방법밖에 없다

그래서 0일때의 점화식은

dp[i][j] = dp[i - 1][j + 1];

9일때의 점화식은

dp[i][j] = dp[i - 1][j - 1];

이렇게 된다

#include <iostream>
using namespace std;
long long dp[101][101];
int main() {
	long long N;
	long long sum = 0;
	cin >> N;
	dp[1][0] = 0;
	for (int i = 1; i <= 9; i++) {
		dp[1][i] = 1;
	}
	
	for (int i = 2; i <= N; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][j + 1];
			}
			else if (j == 9) {
				dp[i][j] = dp[i - 1][j - 1];
			}
			else
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
				
			dp[i][j] = dp[i][j] % 1000000000;
		}

	}

	for (int i = 0; i <= 9; i++) {
		sum += dp[N][i];
		sum %= 1000000000;
	}
	cout << sum;
}

이 두 부분을 제외하고는 이전자리의 수에서 나보다 하나 크거나 하나 작은 곳에서 부터 올수 있으니

2개의 경우 의 수를 합쳐준다 즉

3번째 자리에 3은 2번째자리에 2와 4로부터 오는것이니 [2][4]+[2][2]를 하면 된다

그래서 이부분의 점화식은

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];

이렇게 된다. 하지만 숫자가 너무 커지게 되니 이 연산이 끝나고 나면 모듈러 연산을 해주면 좋다