[백준] 10844번 쉬운 계단 수 C/C++ 풀이

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

10844번: 쉬운 계단 수

 

풀이

우선 이 문제를 해결하는데 많은 시간이 걸렸다.

이 계단수는 특별한 규칙을 갖고있다. 한번 찾아보도록 하자.

45676(O)  890(X)  709(X)

$$(n=자릿수, \quad C=계단\:수)$$

\(n=1\)일 경우, 다음과 같다. \(C=9\)

1, 2, 3, 4, 5, 6, 7, 8, 9

 

\(n=2\)일 경우, 다음과 같다. \(C=17\)

10, 12

21, 23

32, 34

43, 45,

54, 56

65, 67

76, 78

87, 89

98

 

\(n=3\)일 경우, 다음과 같다. \(C=32\)

101, 121, 123

210, 212, 232, 234 ...

987, 989

 

이 식에 점화식은 총 3개이다. \(Kn = n열\)

If K0,
  arr[i][q] = arr[i - 1][q + 1]
If K1~K8,
  arr[i][q] = arr[i - 1][q - 1] + arr[i - 1][q + 1] % 1000000000
If K9,
  arr[i][q] = arr[i - 1][q - 1]

 

C/C++ 풀이