👉문제
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
👉입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
예시 - 2
👉출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
예시 - 17
👉문제 이해
연달아 있는 숫자끼리의 차가 1이여야하고, N은 해당 숫자의 자릿수를 의미한다.
만약 N이 1이면 1, 2, 3, 4, 5, 6, 7, 8, 9로 총 9개 (문제에서 0으로 시작하는 수는 없다고 주어졌기 때문에 0은 해당 안됨)
마찬가지로 N이 2이면 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98로 총 17개!
✍내 풀이
import java.util.*;
public class Main {
static int[][] arr = new int[101][10];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(stair(n));
}
static int stair(int n) {
arr[1][0] = 0;
for( int i = 1 ; i <= 9 ; i++) arr[1][i] = 1;
int ans = 0 ;
for(int i = 2 ; i <=n ; i ++ ) {
arr[i][0] = arr[i-1][1];
arr[i][9] = arr[i-1][8];
for( int j = 1 ; j < 9 ; j ++) {
arr[i][j] = (arr[i-1][j-1] + arr[i-1][j+1]) % 1000000000 ;
}
}
for(int i = 0 ; i <=9 ; i++) {
ans = (ans + arr[n][i]) % 1000000000 ;
}
return ans;
}
}
✍Note
-
실패한 접근😭
숫자를 N별로 쭉 써보고 1로 끝나는 숫자의 갯수, 0으로 끝나는 수의 갯수, 9로 끝나는 수의 갯수를 찾아 규칙을 찾아보려 했으나 규칙은 없었음,,
결국 다른 사람들의 방법을 참고했다. 방법은 다음과 같다. -
참고한 방법🙌
이전 단계에서의 끝자리 숫자들에 따라서 해당 단계에서의 경우의 수를 따져야 하기 때문에 단계와 끝자리 숫자를 배열의 index로, 그 배열에는 그 단계에서 그 끝자리 숫자로 끝나는 숫자들의 갯수를 넣는다.
예를 들어 N이 2일때 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98로 총 17개라고 하였다. 이때 배열의 이름이 arr라고 하면 0으로 끝나는 숫자는 10으로 한가지이기 때문에 arr[2][0]에는 1, 1로 끝나는 숫자는 21로 한가지이기 때문에 arr[2][1]에는 1, 2로 끝나는 숫자는 12, 32로 두가지이기 때문에 arr[2][2]에는 2가 저장된다.
만약 해당단계가 3이고 끝자리가 4일 때 숫자의 갯수를 찾는 방법은
arr[3][4] = arr[2][3] + arr[2][5] 로
이전 단계 (2단계)에서 끝자리 숫자가 4와 차이가 1인 3과 5일 때의 숫자의 갯수를 더하는 것이다.
즉 점화식은
arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1] ( j>=1 && j<=8)
arr[i][j] = arr[i-1][j+1] ( j == 0 )
arr[i][j] = arr[i-1][j-1] ( j == 9 )
이다.
👆따져야 하는 경우가 2가지일 때 2차원 배열을 사용하는 방법도 생각해봐야 할 듯 싶다.
