백준 10844 자바 - 쉬운 계단 수

문제

---

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

10844번: 쉬운 계단 수

 

 

 

문제해결

---

- dp를 2차원 배열로 만들어 1차원에는 자리수, 2차원에는 맨 오른쪽 숫자를 표현하고 값은 각각 0~9로 끝나는 계단수의 개수를 저장한다

- n이 1일경우(한자리수일 경우) 0을 제외한 1~9이기 때문에 1로 초기화 한다

 

- 2자리수의 끝이 5인 계단수는 1자리수인 4, 6에 +1, -1한 값인 45, 65이다

- 맨 오른쪽 숫자가 0일경우 그 전 자리수의 1에 -1한 값만 올수 있다(1->10)

- 맨 오른쪽 숫자가 9일경우 그 전 자리수의 8에 +1한 값만 올수 있다(8->89)

 

- 이 규칙을 따라 아래와 같이 점화식을 구할 수 있다

dp[i][0] = dp[i-1][1]

dp[i][9] = dp[i-1][8]

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

import java.util.Scanner;

public class B10844_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //1차원: 자리수(n), 2차원: 맨 오른쪽 숫자(0~9), 값은 개수가 들어간다
        int[][] dp = new int[n+1][10];
        //0을 제외한 한자리수 숫자는 자기 자신밖에 없으므로 1로 초기화 
        for (int i = 1; i <= 9; i++) {
            dp[1][i] = 1;
        }
        //2~n 자리수 까지 맨 오른쪽 숫자가 0~9일때의 값을 저장한다
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
                //맨 오른쪽 숫자가 0일땐 그 전 자리수가 1로 끝날때 밖에 없음
                if (j==0) dp[i][0] = dp[i-1][1];
                //맨 오른쪽 숫자가 9일떈 그 전 자리수가 8로 끝날때 밖에 없음
                else if (j==9) dp[i][9] = dp[i-1][8];
                //그 전 자리수의 j-1에 +1한 값, j+1에 -1한값의 개수
                else dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
                dp[i][j] %= 1000000000;
            }
        }
        //n 자리수 일때 모든 계단수
        int result = 0;
        for (int i = 0; i <= 9; i++) {
            result += dp[n][i];
            result %= 1000000000;
        }
        System.out.println(result % 1000000000);
    }
}

참고:

https://yabmoons.tistory.com/515

[ 백준 10844 ] 쉬운 계단 수 (C++)

 

https://st-lab.tistory.com/134

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