[C/C++] 백준 10844번 - 쉬운 계단 수(DP)

 

<DP코드>

#include <algorithm>
#include <iostream>
using namespace std;

long long DP[101][10];
int N;
long long ans = 0;

int main()
{
	//한자리수들 1로 지정
	for (int i = 0; i <= 9; i++) DP[1][i] = 1; 
	
	cin >> N;

	//두자리수 이상일때
	for (int i = 2; i <= N; i++)
	{
		DP[i][0] = (DP[i - 1][1]) % 1000000000;
		DP[i][9] = (DP[i - 1][8]) % 1000000000;

		for (int j = 1; j <= 8; j++)
			DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % 1000000000;	
	}

	//맨 앞자리가 각각 i일때 DP값을 취합
	for (int i = 1; i <= 9; i++) ans += DP[N][i];

	cout << ans % 1000000000;
}

코드가 계속 틀렸다고 나와서 입력값으로 100을 넣어보니 음수가 나왔다. 즉, long long 자료형의 범위를 넘어서는 값까지 올라간다는 얘기였다. 그리고 DP를 10억으로 나눴음에도 ans를 다시 10억으로 나눠주는 이유는 DP값들을 더했을 때 ans값이 또 10억을 넘을 수 있기 때문에 마지막 출력전에 한번더 10억으로 나눠준다. 

 

 

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수