[백준 - 10844] 쉬운 계단 수

#include <iostream>
#define MOD 1000000000
using namespace std;
long long DP[101][11] = {0,};

int main()
{
	//1. Get input value & Set initial value for DP table
	ios::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;

	for (int i = 0; i <= 9; ++i)
	{
		DP[1][i] = 1;
	}

	//2. Do Loop
	for (int i = 2; i <= 100; ++i)
	{
		DP[i][0] = DP[i - 1][1];
		for (int j = 1; j <= 9; ++j)
		{
			DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % MOD;
		}
	}

	//3. Print
	long long result = 0;
	for (int i = 1; i <= 9; ++i)
	{
		result += DP[N][i];
	}
	cout << result % MOD;
	return 0;
}

---

||사고 과정

내가 풀지 못한 문제다.

다만 옳은 방법이 생각 났음 에도 아닌거 같아 시도 하지 않았다ㅠ

 

처음에는 일차원 배열에 각 N마다 나올 수 있는 최대수를 저장한다고 생각했다.

근데 아무리 봐도 이렇게 테이블을 구성하면 안된다고 생각이 들었다.

 

그래서 i - 1자리에 있는 수를 이용하는 이차원 배열로 테이블을 구성하자고 생각했다.

이게 맞는데 처음에 초기값 세팅을 DP[1][1] = 1; DP[1][2] = 1; ......DP[1][9] = 1; 이렇게 

모두 쓰니까 뭔가 이게 아닌가..?? 느낌이  들어서 삭제했다.....ㅠ

시험 볼때 모두 체크한 답이 모두 4번이면 이상한 느낌이 드는것처럼..

 

아쉽지만 내가 정확한 점화식을 써놓지 않아서 그렇다고 생각한다!

---

||사용 기법

• DP

---

||풀면서 느낀 것

• 점화식 잘 세우기!

정말 몇가지 안되는 예로 점화식 세우는 연습을 많이 해야겠다.

지금 나는 너무 많은 예로 확실히 확인을 하려함

• 이상해도 끝까지 가보기!