Baekjoon10844: 쉬운 계단 수

쉬운 계단 수 

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

88847

27395

19614

28.884%

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

풀이

논리는 재귀의 방법으로 생각할 수 있다. 반복문이나 메소드를 통해 만들 수 있다.(Top↔Bottom)

1) □□□□□□□□□□□□□□

우선 맨 뒷자리부터 시작한다. 처음에는 0~9가 다양하게 올 수 있고 마지막 항에는 0이 오지 못한다.

2) □□□□□□□□□□□□□■

맨 뒷자리에 만약 9가 오면? 그 앞은 8을 적어야만 한다.

맨 뒷자리에 0이 오면? 그 앞은 1을 적어야만 한다.

 

반복문 만들기

맨 앞자리를 0항, 맨 뒷자리를 입력받은 N항이라고 한다. 맨 앞자리(0항)에는 0이 올 수 없다. dp[0][0]=0;

현재항의 숫자가 9라면 이전항의 8의 값을 호출한다. 현재항의 숫자가 0이면 이전항의 1을 호출한다.

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		double mod = 1000000000; //나머지 연산
		Double[][] dp=new Double[N][10]; //워낙 숫자가 크므로 더블로 생성
		for(int i=1; i<10;i++)dp[0][i]=1.0; //double이므로 1.0
		dp[0][0]=0.0; //맨 앞자리가 0인 경우는 없다
		for(int i=0; i<N;i++) {
			for(int j=0; j<10; j++) {
				if(dp[i][j]==null) {
                
				if(j==0)dp[i][j]=dp[i-1][1]%mod; //0인 경우 앞자리는 1이된다
                
				else if(j==9)dp[i][j]=dp[i-1][8]%mod; //9인 경우 앞자리는 8
                
				else dp[i][j]=(dp[i-1][j+1]+dp[i-1][j-1])%mod;}}}
                //나머지 숫자들은 계단의 경우가 2가지 있으므로 두 개의 경우를 더해준다
		double sum=0;
		for(int i=0; i<10;i++)sum+=dp[N-1][i]%mod;
    	//첫째자리 0~9를 적는 모든 경우의 수를 더해야 전체 경우의 수를 얻을 수 있다.
		System.out.println(String.format("%.0f",sum%mod));}}