Baekjoon10844-쉬운 계단 수

백준 사이트 10844 - 쉬운 계단 수 문제입니다.

---

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

dp문제입니다. 어려운 dp문제는 아니지만 예외처리를 잘 해줘야합니다. 백준에서는 Sliver1의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

1. 입력크기가 n이면 100자리 수라 입력을 string으로 받아야할까라고 생각했지만, 일단 1부터 넣어서 특징을 찾기로 했습니다.
2. 끝자리가 0일때, 9일 때 조심해야합니다.

구상도는 밑과 같습니다..

설명을 매끄럽게 못하겠지만, 위를 참고로 어떤 의미인지 찾아가시면 좋겠습니다.

---

5. code

//주석은 바로 밑의 코드에 대한 설명입니다.
#include<iostream>

using namespace std;

const int row = 101;
// 만약 j가 9일 때 10인덱스에 접근해도 0을 더할 수 있게 도와준다.
const int col = 11;
int result[row][col] = { 0, };

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	long long count = 9;
	for (int i = 1; i < 10; ++i)
		result[1][i] = 1;
	for (int i = 2; i <= n; ++i)
	{
		count = 0;
		result[i][0] += result[i - 1][1];
		count += result[i][0];
		for (int j = 1; j < 10; ++j)
		{
			result[i][j] = (result[i - 1][j - 1] + result[i - 1][j + 1])%1000000000;
			//확인용			cout << j << " " << result[i][j] << '\n';
			count += result[i][j];
		}
	}
    // 해주는 이유는 count가 위에서 계속 더해지므로 언제 10억을 넘어갈 지 모름 마지막에 다시 10억으로 나눠줘야한다.
	cout << count% 1000000000; 
}

---

6. 후기

크게 어렵지는 않았다.