[BOJ] 10844번 쉬운 계단 수(C++) - 오버플로우 조심!

풀이 소요시간 : 40분

풀이 방식의 구상에 5분, 구현에 10분, total의 타입을 long long 으로 하지 않아서 삽질 25분..
DP 문제는 int 값을 벗어나는 경우가 허다한듯하다. 심지어 정답을 10억으로 나눈 나머지를 출력하는 문제였던지라 int 범위를 벗어날 줄은 몰랐다.

애초에 10억을 1억으로 잘못 읽어서 발생한 문제.
약 21억을 넘어가는 순간 int 타입에서는 오버플로우가 발생하기 때문에, long long 타입을 걸어줘야한다.

전체 코드

#include<iostream>
using namespace std;
#define MOD 1000000000

int N;
int DP[101][10];

void Init() {

	//길이가 1인 계단 수 초기화
	DP[1][0] = 0;
	for (int i = 1; i <= 9; i++) {
		DP[1][i] = 1;
	}
	
	//길이가 2 - 100 인 계단 수 초기화
	for (int i = 2; i <= 100; i++) {

		for (int j = 0; j <= 9; j++) {

			if (j == 0) {
				DP[i][j] = DP[i - 1][j + 1] % MOD;
			}
			else if (j == 9) {
				DP[i][j] = DP[i - 1][j - 1] % MOD;
			}
			else {
				DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % MOD;
			}
		}
	}
}



int main() {

	Init();

	cin >> N;
	long long total = 0;
	for (int i = 0; i <= 9; i++) {
		total += DP[N][i];
	}
	cout << (total % 1000000000) << endl;
    
}