Programming/백준 문제풀이
[백준] 10844번 쉬운 계단 수 C/C++ 풀이
bjloed
2020. 4. 24. 15:41
출처: https://www.acmicpc.net/problem/10844
10844번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
풀이
우선 이 문제를 해결하는데 많은 시간이 걸렸다.
이 계단수는 특별한 규칙을 갖고있다. 한번 찾아보도록 하자.
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++ 풀이
