백준 - 10844번 쉬운 계단 수

문제

인접한 자리수의 차가 1인 수를 계단 수라고 할 때
길이가 N인 계단 수의 개수는?

생각

틀렸습니다 1

길이가 i인 계단 수의 총 개수를 알면,
길이가 i+1일 때는 어떤지 알기 쉬울 거라고 생각해서
dp[i]에 길이가 i일 때 계단 수가 총 몇 개 있는지 저장해서 문제를 해결하려고 했다

예를들어 길이 i일 때 맨 오른쪽 수가 3이면
오른쪽에 2, 4를 붙여서 길이가 i+1인 계단 수를 만들 수 있으니까!

그래서 처음엔 간단히 1~8은 인접수가 2개니까 전에 경우의 수보다 2배가 되는데,
0이랑 9는 인접수가 1개니까 2개 부족할 듯? 이라는 생각으로
아래와 같이 구현을 했었다

for (int i = 2; i < n; i++) {
    dp[i + 1] = 2 * dp[i] - 2;
}

근데 틀렸당
다시 생각해보니 -2는 너무 멍청했었음ㅋㅋ
길이가 i일 때 맨 오른쪽 수가 0, 9인 경우의 수 만큼 빼주는 것도 아니고?
라는 생각이 들었다

틀렸습니다 2

그렇다 사실 맨 오른쪽 수에 따라서 그 다음에 만들 수 있는 수가 정해져있으니까
맨 오른쪽 수에 대한 정보도 dp 배열에 표시해줘야한다고 생각이 들었다
dp[j][i]에 길이가 j일 때 맨 오른쪽 수가 i인 계단 수가 총 몇 개를 저장해야지!

예를들어 길이 j+1일 때 맨 오른쪽 수가 3인 경우는
길이 j 일 때 맨 오른쪽 수가 2인 경우, 4인 경우 만들 수 있으니까!

수정한 코드는 이거다

for (int j = 2; j <= n; j++) {
    dp[j][0] = dp[j-1][1]; //0은 1에 의해서만 만들어지고
    dp[j][9] = dp[j-1][8]; //9는 8에 의해서만 만들어진다
    for (int i = 1; i < 9; i++) {//1~8은 양 옆 인접수로 만들어졌겠징!
        dp[j][i] = dp[j - 1][i - 1] + dp[j - 1][i + 1];
    }
}

논리는 맞았는데, 자료형 크기가 문제였당

맞았습니다

왜 틀렸을까 디버깅을 해보니까 n이 엄청 큰 경우 오버플로우 되더라!
정답을 엄청 큰 수로 나누라고 하기도 했고, 설마 오버플로우!? 했는데 설마가 맞았다

자료형의 범위는 int는 2^31 long long은 2^63!
이거 둘 다 어마무시하게 큰 수긴 한데

dp배열에 저장되는 값이 대충 2배씩 커진다고 하면
n이 최대로 들어오는 경우에 2^100 정도로 값이 커진다
그래서 dp 배열을 long long으로 선언을 해도 오버플로우임

따라서 출력값이 결과를 10억으로 나눈값이니까,
dp배열에 저장할 때도 10억으로 나눠서 저장하게 했다

dp[j][i] = (dp[j - 1][i - 1] + dp[j - 1][i + 1]) % 1000000000;

또한 dp[j][i]에서 i가 0~9인 모든 값을 다 합친 결과가 j 길이일 때 최대 계단 수 이므로
아래와 같이 for문을 돌면서 결과를 구하는데,

for (int i = 0; i < 10; i++) {
    result += dp[n][i];
}

result가 int 자료형인 경우 배열에 10억 이상인 애들이 있으면 또 오버플로우가 나게된다!
result는 long long으로 선언해줘야해~~!

이러면 맞았습니다~된다!!

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int n;
long long result;
int dp[105][10];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;

	for (int i = 1; i < 10; i++) {
		dp[1][i]++;
	}

	for (int j = 2; j <= n; j++) {
		dp[j][0] = dp[j-1][1];
		dp[j][9] = dp[j-1][8];
		for (int i = 1; i < 9; i++) {
			dp[j][i] = (dp[j - 1][i - 1] + dp[j - 1][i + 1]) % 1000000000;
		}
	}

	for (int i = 0; i < 10; i++) {
		result += dp[n][i];
	}
	
	cout << result % 1000000000;

	return 0;
}