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

문제링크: https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

전형적인 DP 문제였습니다.

1~9로 시작하는 값에 대한 테이블입니다.

 

	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
2	2	2	2	2	2	2	2	2	1
3	3	4	4	4	4	4	4	3	2
4	6	7	8	8	8	8	7	6	3

즉, 1로 시작하는 네자리수는 5개 입니다. ( 1010, 1012, 1212, 1210, 1232, 1234)

 

이때    101~ 는  dp[2][1] 이구 12~ 는 dp[3][2] 입니다.

 

그외에 2~8로 시작하는 네자리수는 dp[i][j] = dp[i-1][j-1]+ dp[i-1][j+1]임을 확인할 수 있습니다. 

 

9로 시작할때는 98~이니 dp[i][j] = dp[i-1][j-1]

 

 즉 점화식은

arr[i][j] = arr[i - 1][j + 1] + arr[i - 2][j] (i=1일떄)

arr[i][j] = arr[i - 1][j + 1] + arr[i - 1][j - 1] (2~8)

arr[i][j] = arr[i - 1][j - 1] (i=9)

 

 

#include <iostream>
using namespace std;
int arr[101][10] = { 0 };
long long result = 0;
int n = 0;
int main() {
	cin >> n;	

	for (int i = 1; i <= 9; i++) // 초기값 설정
		arr[1][i] = 1;
	for (int j = 1; j <= 8; j++)
		arr[2][j] = 2;
	arr[2][9] = 1;

	for (int i = 3; i <= n; i++) {
		for (int j = 1; j <= 9; j++) {
			if (j == 1)
				arr[i][j] = (arr[i - 1][j + 1] + arr[i - 2][j]) % 1000000000;
			else if(j==9)
				arr[i][j] = (arr[i - 1][j - 1]) % 1000000000;
			else 
				arr[i][j] = (arr[i - 1][j + 1] + arr[i - 1][j - 1]) % 1000000000;
			
		}
	}

	for (int i = 1; i <= 9; i++) {
		result += arr[n][i];
	}
	result %= 1000000000;

	cout << result << endl;
}

arr 연산식마다 %1000000000 를 해주어야 오버플로우를 피할 수 있습니다. int 형의 범위를 넘어갈 수 있기 때문입니다.

반면 result는 long long 형으로 정의했기 때문에 1~9까지의 값을 다 더하고 나눠도 지장이 없습니다.

 

위 테이블을 보고 직접 점화식을 유추해보세요! 화이팅!