10844) 쉬운 계단의 수 (C++)

 출처 

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

10844번: 쉬운 계단 수

 내 풀이 

#include<iostream>

using namespace std;

int N = 0;

int DP[101][10];
long long result = 0;
int main()
{
	cin >> N;

	//N이 1일 경우 1 대입 
	for (int i = 1; i <= 9; i++)
	{
		DP[1][i] = 1;
	}


	for (int i = 2; i <= N; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			if (j == 0) DP[i][j] = DP[i - 1][1];
			else if (j == 9) DP[i][j] = DP[i - 1][8];
			else DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % 1000000000;
		}
	}

	for (int i = 0; i <= 9; i++)
	{
		result = (result + DP[N][i]) % 1000000000;
	}

	result %= 1000000000;
	cout << result;
}

 

 해설

접은 글을 확인하여 보면 공식이 나온다. 

 

2번 째 자리 수부터

0이 뒤에 올 수 있는 경우의 수 = 앞자리가 1인 경우

1이 뒤에 올 수 있는 경우의 수 = 앞자리가 2인 경우

2~8 = N이 뒤에 올 수 있는 경우의 수 = 앞자리가 N-1, N+1인 경우

9가 뒤에 올 수 있는 경우의 수  = 앞자리가 8인 경우 

 

이러한 공식이 나온다. 이 공식을 이용하여 문제를 풀어보았다. 

 

 

 느낀 점 

쉬운 계단 완전 구라였다. 너무 어려웠다. 엄청 어려웠다.

1시간 동안 메모장을 켜서 계속 고민 고민해도 공식을 찾을 수 없었다. 

결국 검색을 한 끝에 해설을 한번 참고하고 문제를 풀어보니 다행히 예제 문제는 맞는 출력이 나왔다.

하지만 제출 후 결과를 본 나는 어떻게든 바꿔서 제출해도 틀렸다고 나와서 멘탈이 터져버렸다.

결국 다시 해설을 봤던 블로그에 다시 들어가 소스코드를 다시 보고 이해했다. 

그렇다. 도중에도 long long 형을 초과할 수도 있다는 것이었다. 악마같은 문제였다.

 

엄청난 자신감 하락