티스토리 뷰
https://www.acmicpc.net/problem/10844
45656 이라는 숫자가 존재한다고 할때 4는 1번째 자리 수, 5는 2번째 자리 수 6은 3번째 자리 수, 5는 4번째 자리 수, 6은 5번째 자리 수로 표현할 수 있다.
n번째 자리 수가 0일경우 n+1번째 자리수는 1만 가능하며 n번째 자리 수가 9일 경우 n+1번째 자리수는 8만 가능하다.
n번째 자리 수가 1~8인 경우는 n+1번째 자리수에 각각 2개의 숫자가 존재할 수 있다. (예: n번째 자리 수가 1인경우 0 또는 2, n번째 자리 수가 4인경우 3 또는 5)
즉,
n+1번째 자리에서 0이 나올 수 있는 경우의 수 <- n번째 자리에서 1이 나올 수 있는 경우의 수
n+1번째 자리에서 1이 나올 수 있는 경우의 수 <- n번째 자리에서 0이 나올 수 있는 경우의 수 + n번째 자리에서 2가 나올 수 있는 경우의 수
...
n+1번째 자리에서 8이 나올 수 있는 경우의 수 <- n번째 자리에서 7이 나올 수 있는 경우의 수 + n번째 자리에서 9이 나올 수 있는 경우의 수
n+1번째 자리에서 9가 나올 수 있는 경우의 수 <- n번째 자리에서 8이 나올 수 있는 경우의 수
마지막에 N번째 자리에서 0~9가 나올 수 있는 경우의 수를 모두 더하면 길이가 N인 계단 수가 된다.
점화식
arr[1][0] = 0
arr[1][1:9] = 1
arr[n][0] = arr[n-1][1]
arr[n][1] = arr[n-1][0] + arr[n-1][2]
arr[n][2] = arr[n-1][1] + arr[n-1][3]
arr[n][3] = arr[n-1][2] + arr[n-1][4]
arr[n][4] = arr[n-1][3] + arr[n-1][5]
arr[n][5] = arr[n-1][4] + arr[n-1][6]
arr[n][6] = arr[n-1][5] + arr[n-1][7]
arr[n][7] = arr[n-1][6] + arr[n-1][8]
arr[n][8] = arr[n-1][7] + arr[n-1][9]
arr[n][9] = arr[n-1][8]
C++ code
n번째 숫자를 구하기 위해서는 n-1번째 숫자만 필요하고 그 이전 숫자에 대한 정보는 필요 없으므로
행 2개만 사용하여 번갈아가며 정보를 저장할 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #include <iostream> using namespace std; int main(){ int n; cin >> n; unsigned int arr[2][10]; arr[0][0] = 0; for(int i = 1; i < 10; i++){ arr[0][i] = 1; } for(int i = 0; i < 10; i++){ arr[1][i] = 0; } int j = 0; for(int i = 1; i < n; i++){ j = !j; arr[j][0] = arr[!j][1] % 1000000000; for(int k = 1; k < 9; ++k){ arr[j][k] = (arr[!j][k-1] + arr[!j][k+1]) % 1000000000; } arr[j][9] = arr[!j][8] % 1000000000; } int answer = 0; for(int i = 0; i < 10; i++){ answer = (answer + arr[j][i]) % 1000000000; } cout << answer; return 0; } | cs |