[JAVA] 백준 10844 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

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

- N이 주어질 때, 길이가 N인 계단 수가 총 몇개 있는지 구해보자

- 0으로 시작하는 수는 계단 수가 아니다. 

 

 

풀이 과정 

 

n이 1일 떄 

- 1,2,3,4,5,6,7,8,9

- 9개

 

n이 2일 때 

- 12,23,34,45,56,67,78,89,21,32,43,54,65,76,87,98,10

- 17개

 

 

[백준] 10844번 : 쉬운 계단 수 - JAVA [자바] (tistory.com)

[백준] 10844번 : 쉬운 계단 수 - JAVA [자바]

 

- n번째 자릿수 

 -> 길이가 n인 자연수에서 가장 왼쪽에 있는 수가 n번째 자리가 n번째가 됨

 

1) n번째 자릿수의 자릿값이 0인 경우

 - 다음 자릿수의 자릿값은 1밖에 올 수 없음

 

2) n번째 자릿수의 자릿값이 9인 경우 

- 다음 자릿수의 자릿값은 8밖에 올 수 없음 

 

3) 그외의 값(2~8)

- 각 값보다 -1 또는 +1인 값을 가질 수 있음

 

- memo[][]는 2차원 배열이고 memo[자리 수][n번째 자릿수]

 

- Top-Down 방식으로 동적 프로그래밍으로 풀이 

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    static Long memo[][];
    static int n;
    final static long MOD = 1000000000;
    
    //digit는 자릿수, val은 자릿값을 의미
    static long df(int digit, int val)
    {
        //첫째 자릿수에 도착한다면 더이상 탐색할 필요 없음
        if(digit == 1)
        {
            return memo[digit][val];
        }
        
        //해당 자릿수의 val값에 대해 탐색하지 않았을 경우 
        if(memo[digit][val]==null)
        {
            //val이 0일 경우 이전 자리는 1밖에 오지 못함
            if(val==0)
            {
                memo[digit][val] = df(digit-1,1);
            }
            //val이 1일 경우 이전은 8밖에 오지 못함
            else if(val==9)
            {
                memo[digit][val] = df(digit-1,8);
            }
            //그 외의 경우에는 val-1과 val+1의 값의 경우의 수를 합한 수가 됨
            else
            {
                memo[digit][val] = df(digit-1,val-1)+df(digit-1,val+1);
            }
        }
        return memo[digit][val]%MOD;
    }
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        n = Integer.parseInt(br.readLine());
        
        memo = new Long[n+1][10];
        
        //첫 번째 자릿수 1로 초기화
        for(int i=0; i<10; i++)
        {
            memo[1][i] = 1L;
        }
        
        long result = 0;
        
        //마지막 자릿수인 1~9까지의 경우의 수를 모두 더함 
        for(int i=1; i<=9; i++)
        {
            result += df(n,i);
        }
        
        bw.write(String.valueOf(result%MOD));
        bw.flush();
        bw.close();
    }
}