[DP] BOJ 10844 쉬운 계단 수 - 오답노트

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

10844번: 쉬운 계단 수

- 문제 파악

이웃한 자리수의 숫자의 차가 1인 수를 계단 수라고 한다. 정수 N이 주어졌을 때, N자리 계단 수를 만들 경우의 수를 구하여라. (0으로 시작하는 계단수는 없음, 0 이전의 수는 없음, 9 다음의 수는 없음)

 

- 나의 접근

N 자리일때 2^(N-1)의 경우가 생기는데 여기서 위와 같은 경우를 빼는 식으로 접근

배열로 안풀려도 풀릴거 같아서 위와 같은 방법으로 접근 했지만 DP 는 배열을 선언해야한다.

 

- 정답

D[i][j] 는 i 번째 자리에 j 가 오는 경우

D[i][j] 는 D[i][j-1] + D[i][j+1] 이다. (j 다음에 +1,-1이 되는 수가 올 수 있으므로)

D[i][j] 에서 j 가 0 일 때, D[i][j] 는 D[i][j+1] 이다. (0 다음에 1 만 올 수 있으므로)

D[i][j] 에서 j 가 9 일 때, D[i][j] 는 D[i][j-1] 이다. (9 다음에 8만 올 수 있으므로)

 

그리고 ans 를 계산할때 D[i][j]를 구하는 for문에서 계산하여 제출 했을 때는 틀렸고,

따로 D[N][j]를 구하는 for문을 만들어서 제출 했을 때는 맞았다.

(이유는 모름..)

 

 

#include "bits/stdc++.h"

#define ANS 1000000000

using namespace std;

int n;
unsigned long long D[101][11]; // D[i][j] i -> n번째 , j -> n 번째에 오는 수
unsigned long long ans;

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;

	for (int i = 1; i < 10; i++)
		D[1][i] = 1;

	for (int i = 2; i <= n; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			if (j == 0)
			{
				D[i][j] = D[i - 1][j + 1] % ANS;
			}
			else if (j == 9)
			{
				D[i][j] = D[i - 1][j - 1] % ANS;
			}
			else
			{
				D[i][j] = (D[i - 1][j + 1] + D[i - 1][j - 1]) % ANS;
			}		
		}
	}

	for (int i = 0; i < 10; i++)
		ans = (ans + D[n][i]) % ANS;

	cout << ans;

}