백준 10844번: 쉬운 계단 수

백준 10844번: 쉬운 계단 수

문제

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

인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다. 단, 0으로 시작하는 수는 계단수가 아니다.

1 이상 100 이하의 자연수 N이 주어질 때, N자리의 계단수의 개수 1,000,000,000으로 나눈 나머지를 구하는 문제이다.

풀이

끝자리가 0인 경우에는 그 다음으로 올 수 있는 숫자는 1이고, 9인 경우에는 8이다. 그 외인 1 이상 8 이하의 정수 K 다음으로는 K-1, K+1이 올 수 있다.

N+1 * 10 크기의 2차원 배열 dp를 만들어, dp[n][k]에 자릿수가 n이고, 끝자리 수가 k인 계단수의 개수를 저장한다. k가 1 이상 8 이하일 때는 dp[n][k-1]과 dp[n][k+1]에 dp[n-1][k]를 더해주고, k가 0과 9인 경우에는 각각 [n][1]과 [n][8]에만 dp[n-1][k]를 더해준다.

코드

C++

#include typedef unsigned long long ull; int main() { int n; scanf("%d", &n;); ull **dp = new ull*[n+1]; for(int i=0; i<=n; i++) { dp[i] = new ull[10]; for(int j=0; j<10; j++) dp[i][j] = 0; } for(int i=1; i<10; i++) dp[1][i] = 1; for(int i=2; i<=n; i++) { for(int j=1; j<9; j++) { dp[i][j-1] += dp[i-1][j]; dp[i][j-1] %= 1000000000; dp[i][j+1] += dp[i-1][j]; dp[i][j+1] %= 1000000000; } dp[i][1] += dp[i-1][0]; dp[i][1] %= 1000000000; dp[i][8] += dp[i-1][9]; dp[i][8] %= 1000000000; } int answer = 0; for(int i=0; i<10; i++) { answer += dp[n][i]; answer %= 1000000000; } printf("%d

", answer); for(int i=0; i<=n; i++) delete[] dp[i]; delete[] dp; return 0; }

Java

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long[][] dp = new long[n+1][10]; for(int i=0; i<=n; i++) for(int j=0; j<10; j++) dp[i][j] = 0; for(int i=1; i<10; i++) dp[1][i] = 1; for(int i=2; i<=n; i++) { for(int j=1; j<9; j++) { dp[i][j-1] += dp[i-1][j]; dp[i][j-1] %= 1000000000; dp[i][j+1] += dp[i-1][j]; dp[i][j+1] %= 1000000000; } dp[i][1] += dp[i-1][0]; dp[i][1] %= 1000000000; dp[i][8] += dp[i-1][9]; dp[i][8] %= 1000000000; } int answer = 0; for(int i=0; i<10; i++) { answer += dp[n][i]; answer %= 1000000000; } System.out.println(answer); } }

Python

n = int(input()) dp = [[0 for _ in range(10)] for _ in range(n+1)] for i in range(1, 10): dp[1][i] = 1 for i in range(2, n+1): for j in range(1, 9): dp[i][j-1] += dp[i-1][j] dp[i][j-1] %= 1000000000 dp[i][j+1] += dp[i-1][j] dp[i][j-1] %= 1000000000 dp[i][1] += dp[i-1][0] dp[i][1] %= 1000000000 dp[i][8] += dp[i-1][9] dp[i][8] %= 1000000000 print(sum(dp[n])%1000000000)

from http://hyeonchan.tistory.com/5 by ccl(A) rewrite - 2021-09-14 21:26:44