[백준 BOJ 10844번] 쉬운 계단 수

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

 

1. 문제

 

45656이란 수를 보자.

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

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

---

2. 입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

1

2

---

3. 출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

9

17

---

4. 풀이

이 문제는 풀이에 있어서 다음 2가지 기본적인 규칙만 코드로 잘 구현해두면 작성하기 쉽다.

 

1. 가장 큰자리에는 0이 올 수 없다. 2. 앞에 작성된 숫자가 9나 0이면 현재 자리수에는 8이나 1밖에 적을 수 없다.

 

이들을 처음 시작하는 값이 가장 큰자리수이냐(Top-Down) 작은 자리수이냐(Bottom-Up)에 따라 구현할 코드의 방식이 바뀐다.

---

5. 소스코드

<Top-Down 방식>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
	static Long [][] dp;
	final static long MOD = 1000000000;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		dp = new Long [N+1][10];

        for(int i=0; i<10; i++) dp[1][i] = 1L; 
        //첫자리(1의자리)에는 어떤 값이 오든 1가지의 경우의 수임. 
        //왼쪽(큰자리수)에서 시작해서 오른쪽(작은자리수)으로 가짓수를 찾아갈 것이니 종착점의 경우의 수는 1가지이다.
        long result = 0;

        for(int i=1; i<10; i++){
            result += caseOf(N,i);
        }

        System.out.println(result%MOD);
    }

    public static long caseOf(int digit, int val){ //caseOf는 digit자릿수에 val이 왔을 때 앞에 자리들은 채우는 경우의 수가 어떻게 됨?을 리턴하는 함수이다.
        
        if(digit == 1) return dp[digit][val];

        if(dp[digit][val] == null){
            if(val == 0) dp[digit][val] = caseOf(digit-1, 1);

            else if(val == 9) dp[digit][val] = caseOf(digit-1, 8);

            else dp[digit][val] = caseOf(digit-1, val+1) + caseOf(digit-1, val-1);
        }

        return dp[digit][val]%MOD;
    }

}

 

<Bottom-Up방식>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
	static Long [][] dp;
	final static long MOD = 1000000000;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		dp = new Long [N+1][10];
        long result = 0;
        for(int i=0; i<10; i++) dp[1][i] = 1L; //첫자리(1의자리)에는 어떤 값이 오든 1가지의 경우의 수임. 오른쪽에서 시작해서 왼쪽으로 가짓수를 찾아갈 것인데 맨 마지막에는 이미 1개로 정해져 있어야 재귀를 통해 다시 원 위치로 돌아올 때 경우의 수를 찾아갈 수 있음.

        for(int i=2; i<=N; i++){
            for(int j=0; j<10; j++){
                if(j == 0) dp[i][j] = dp[i-1][1]%MOD;
                else if(j == 9) dp[i][j] = dp[i-1][8]%MOD;
                else dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])%MOD;
            }
        }

        for(int i=1; i<10; i++){
            result += dp[N][i];
        }
        System.out.println(result%MOD);
    }
}

---

6. 배운 것

주어진 크기(1,000,000,000)를 넘기지 않게 하기 위해 미리 final 상수를 위에 기입해두고 필요할 때마다 나눠주는 모습을 기본적인 스킬로 가져가야겠다.

 

또한, 이전의 DP문제에서도 다뤘었지만 위 <Top-Down방식>에서 쓰인 Long [][]처럼 박싱을 통해 입력받지 않은 것들에 대해 판별 시 null을 사용할 수 있도록 해야겠다.