[백준 10844, Java] 쉬운 계단 수

문제

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

풀이

• f(n) 을 길이가 n인 계단 수의 갯수라고 하자
• 그런다음 f(n-1), 즉 길이가 n-1인 계단 수의 갯수와 길이가 n인 계단 수의 갯수가 어떤 관계인지를 생각하자.
• f(n)은 길이가 n-1 인 계단수의 끝자리에 무엇이 오는 지에 따라 갯수가 정해진다. n-1계단 수의 끝자리가 m이면 n계단 수의 끝자리에 올 수 있는 수는 m-1 또는 m+1 이다.
• d[n][m]을 길이가 n인 계단 수중에 끝자리가 m인 것의 갯수라고 하면 d[n][m] = d[n-1][m-1] + d[n-1][m+1]이다. 이때 m=1인 경우와 m=9인경우는 따로 처리해주면 된다.

주의사항

d[n][m] = d[n-1][m-1] + d[n-1][m+1]을 할때 int 범위를 넘어갈 수 있으므로 long으로 선언해야한다

소스

1. 처음 푼 풀이

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

public class Main{
    public static long[][] stepNums;
    public static int MOD = 1000000000;

    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 length = Integer.parseInt(br.readLine().trim());
        stepNums = new long[length+1][10];
        calculateStepNumCount(length);
        long result = getNumberOfStepNums(length);

        bw.write(String.valueOf(result));
        bw.flush();

        br.close();
        bw.close();
    }

    public static void calculateStepNumCount(int length){
        // stepNums[n][m] = 길이가 n인 계단 수 중에 끝자리가 m인 계단수의 갯수
        // stepNums[n][m] = stepNums[n-1][m-1] + stepNums[n-1][m+1]
        for(int l = 1; l<=length ; l++){
            for(int endNum = 0; endNum<=9; endNum++){
                if(endNum ==0){
                    stepNums[l][endNum] = (stepNums[l-1][endNum+1])%MOD;
                }
                else if(endNum ==9){
                    if(l==1){
                        stepNums[l][endNum] = 1;
                    }
                    else {
                        stepNums[l][endNum] = (stepNums[l-1][endNum-1])%MOD;
                    }
                }
                else{
                    if(l==1){
                        stepNums[l][endNum] = 1;
                    }
                    else{
                        stepNums[l][endNum] = (stepNums[l-1][endNum-1] + stepNums[l-1][endNum+1]) % MOD;
                    }
                }

            }

        }


    }
    public static long getNumberOfStepNums(int n){
        long count = 0 ;
        for(int endNum = 0; endNum<=9 ; endNum++){
            count += stepNums[n][endNum];
        }
        return count%MOD;
    }

}

2. 초기화, 1,9의 예외상황 간단하게 정리

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

public class Main {
    public static long[][] stepNums;
    public static int MOD = 1000000000;
    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 length = Integer.parseInt(br.readLine().trim());
        stepNums = new long[length+1][10];

        getNumberOfStepNums(length);
        long result = getCount(length);

        bw.write(String.valueOf(result));
        bw.flush();

        br.close();
        bw.close();


    }

    public static void getNumberOfStepNums(int length){
        for(int endNum = 1 ; endNum<=9 ; endNum++){
            stepNums[1][endNum] = 1;
        }

        for(int l = 2; l<=length ;l++){
            for(int endNum =0 ; endNum<=9; endNum++){
                if(endNum>=1) stepNums[l][endNum] += stepNums[l-1][endNum-1];
                if(endNum<=8) stepNums[l][endNum] += stepNums[l-1][endNum+1];

                stepNums[l][endNum] %= MOD;
            }
        }
    }

    public static long getCount(int length){
        long result = 0;
        for(int endNum =0 ;endNum<=9;endNum++){
            result += stepNums[length][endNum];
        }
        return result%MOD;
    }
}