[백준] 10844: 쉬운 계단 수

SuKong·2020년 8월 2일
0
post-thumbnail

'10844- 쉬운 계단 수' 문제로 이동!

👉문제

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차원 배열을 사용하는 방법도 생각해봐야 할 듯 싶다.

profile
안녕하세요 🤗

0개의 댓글