[백준] 10844번 쉬운계단 수 - Java, 자바

난이도

실버 1

문제

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

풀이

1. 테이블 정의하기

dp[i][j] = 길이가 i이고, j로 끝나는 수의 계단 수의 개수

2. 점화식 찾기

길이가 1일 때 계단수는 9개입니다.

길이가 2일 때 생각해봅시다.
첫째 자리가 0과 9일 때 뒤에 올 수 있는 수는 0은 1, 9는 8로 각각 한개입니다.
첫째 자리가 1일 때 뒤에 올 수 있는 수는 1-1=0, 1+1=2 처럼 각 수의 각각 1을 빼거나 더한 값으로 총 2개입니다. (첫째자리가 1~8일 때 모두 2개로 동일합니다.)

이 점을 고려해 점화식을 세워봅시다.

• 길이가 i이고 j=0으로 시작하는 수 일 때, dp[i][j] = dp[i-1][j+1]
• 길이가 i이고 j=1~8로 시작하는 수일 때, dp[i][j] = dp[i-1][j+1] + dp[i-1][j+1]
• 길이가 i이고 j=9로 시작하는 수일 때, dp[i][j] = dp[i-1][j-1]

3. 초기값 정하기

        long[][] dp = new long[n + 1][10];
        for (int i = 1; i <= 9; i++) {
            dp[1][i] = 1;
        }

추가적으로 고려할 점

• mod, dp, sum의 타입은 int가 아닌 long으로 지정해줘야 합니다.
• mod로 나눈 나머지를 구하는 식은 dp를 채워나갈 때 그리고 result 출력할 때 적용해야 합니다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        long[][] dp = new long[n + 1][10];

        long mod = 1_000_000_000;

        // 초기값 설정
        // dp[1][0] = 0; // 없어도 됨
        for (int i = 1; i <= 9; i++) {
            dp[1][i] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
                if (j == 0)
                    dp[i][j] = (dp[i - 1][j + 1]) % mod;
                else if (j == 9)
                    dp[i][j] = (dp[i - 1][j - 1]) % mod;
                else
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;

            }
        }

        long sum = 0;
        for (int i = 0; i <= 9; i++) {
            sum += dp[n][i];
        }
        System.out.println(sum % mod);


    }
}