[백준] 쉬운 계단 수 : 10844 : Java - DP (S1)

1. 문제

10844번: 쉬운 계단 수

 

• 길이가 N인 계단 수가 몇 개?
• 계단 수란 인접한 모든 자리의 차이가 1인 수를 말한다.
• 1 <=N <= 100
• 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

---

2. 🤔 어떻게 풀까

DP 문제는 무조건 노트에 하나하나 써본다.

N = 1일 때,  {1, 2, 3, 4, 5, 6, 7, 8, 9}

N이 2일 때, { 10,12 21,22, 32,34, 43,45, 54,56, 65,67, 76,78, 87,89, 98}

잘 보면 1~8로 시작하는 수는 계단 수가 2개씩인데, 오직 9로 시작하는 수만 계단 수가 1개 뿐이다. 

 

이 규칙을 더 살펴보면, 마지막 자리의 숫자가 9와 0일 때는 만들 수 있는 계단의 수가 각 xx98, xx01로가 1개뿐이다. 하지만 나머지 1~8까지는 모두 2개씩이다. 예를 들어 마지막 자리의 숫자가 8일 때, 만들 수 있는 계단의 수는 xx87, xx89로 2개이다. 이와 같은 규칙을 적용하여 점화식을 세우면 다음과 같다. n은 숫자의 길이이고 i는 마지막 자리 수(1~8)일 때 `dp[n][i] = dp[n-1][i-1] + dp[n-1][i+1]` dp는 길이가 n일 때 마지막 숫자가 i인 계단수의 개수를 가리킨다. 코드로 보자.

 

 

 

3. 💡풀이 로직

`count[1]`은 0을 제외하고 모두 1로 초기화 시킨다. 그 후 점화식 대로 개수를 계속 더해가며 길이가 N이 될 때까지 반복한다. 최종적으로 `count[N][i]`를 모두 더하여 결과로 출력한다. 여기서 매우 주의할 점은 매 연산마다 모듈러 연산을 해줘야 한다는 것이다. n이 100이 되버리면 count[N]을 구할 때도 long 타입의 범위를 벗어나 버리기 때문에 매 번 모듈러 연산을 잊지 않고 해줘야한다.

        for(int i=1; i<=9; i++){
            count[1][i] = 1;
        }
        for(int i=2; i<=N; i++){
            // 끝의 자리가 1~8인 숫자의 개수
            for(int j=1; j<=8; j++){
                count[i][j] = count[i-1][j-1] + count[i-1][j+1];
                count[i][j] %=1000000000;
            }
            // 끝의 자리가 0이 숫자의 개수
            count[i][0] = count[i-1][1];
            count[i][0] %=1000000000;
            // 끝의 자리가 9이 숫자의 개수
            count[i][9] = count[i-1][8];
            count[i][9] %=1000000000;
        }
        long sum = 0;
        for(long digit_count : count[N]){
            sum += digit_count;
            sum %=1000000000;
        }

 

 

 

4.  🖥️  전체 코드

import java.io.*;
import java.util.*;

public class Main{


    public static void main(String [] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        long count [][] = new long[101][10];

        for(int i=1; i<=9; i++){
            count[1][i] = 1;
        }
        for(int i=2; i<=N; i++){
            // 끝의 자리가 1~8인 숫자의 개수
            for(int j=1; j<=8; j++){
                count[i][j] = count[i-1][j-1] + count[i-1][j+1];
                count[i][j] %=1000000000;
            }
            // 끝의 자리가 0이 숫자의 개수
            count[i][0] = count[i-1][1];
            count[i][0] %=1000000000;
            // 끝의 자리가 9이 숫자의 개수
            count[i][9] = count[i-1][8];
            count[i][9] %=1000000000;
        }
        long sum = 0;
        for(long digit_count : count[N]){
            sum += digit_count;
            sum %=1000000000;
        }
        bw.write(sum +"\n");
        bw.flush();
    }
}