[BOJ] 10844 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

 

알고리즘: DP

 

시간복잡도: O(N) 

 

 

접근:

1. 계단 수가 총 몇 개 인지 구하기 (가짓수)

2. 계단 수 조건: 인접한 자리 수의 차이가 1

 

-> 1,2 번 조건 모두 Dynamic을 이용하기 좋은 조건들이다. 

    1번은 보통 DP 문제들의 패턴이고 2번도 부분문제로 접근할 수 있기 때문이다.

 

2번 조건을 DP로 접근해보면,

N+1 자리수의 계단 수는 마지막 자리를 제외한 나머지 N 자리수도 계단 수를 만족해야한다.

따라서,  N+1 자리수의 계단 수를 계산하려면 N 자리수 계단수부터 계산해야 하고

결국 bottom-up 방식으로 답을 구할 수 있다.

 

주의)

1~8 은 다음에 올 수 있는 수가 2가지지만,

0, 9는 하나 밖에 못 온다.

 

D[i][j]: 자리 수가 i고 맨 마지막 수가 j인 계단 수의 개수  로 두고 DP 배열을 채워나가면 된다. 

$$답=\ \sum_{k=0}^9 D[N][k]\ mod\ 10^9$$

 

이 문제는 DP 배열을 채울 때 바로 이전 값만 확인하기 때문에 DP 배열 사이즈를 2로 잡고

0->1->0->1 ... 이런 식으로 뒤집어가면서 사용했다.

#include<stdio.h>
int N, i, j, D[2][10], k;
int main()
{
	scanf("%d",&N);
	
	for (i = 1; i < 10; i++)
		D[0][i] = 1;
	
	for (i = 1; i < N; i++)
	{
		k = !k;
		D[k][0] = D[!k][1];
		D[k][9] = D[!k][8];
		for (j = 1; j < 9; j++)
		{
			D[k][j] = D[!k][j-1] + D[!k][j+1];
			if (D[k][j] >= 1000000000)
				D[k][j] -= 1000000000;
		}
	}
	
	for (i = 1; i < 10; i++)
		D[k][0] = (D[k][0] + D[k][i])%1000000000;
	
	printf("%d", D[k][0]);
	return 0;
}

 

---

심화문제:

BOJ 1562 계단 수 https://www.acmicpc.net/problem/1562

1562번: 계단 수