[JAVA 알고리즘]BAEKJOON 10844번 쉬운 계단 수

다이나믹 프로그래밍을 이용해서 문제를 해결하는 문제

---

쉬운 계단 수

---

문제 설명

45656이란 수를 보자.

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

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

제한사항

• 없음

입력

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

출력

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

입출력 예

input	return
1	9
2	17

---

나의 문제풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bufferedReader.readLine());
        bufferedReader.close();

        int[][] stairs = new int[N + 1][10];

        // 0으로 시작하는 수는 계단수가 아니다.
        for(int i = 1; i <= 9; i++) {
            stairs[1][i] = 1;
        }

        for(int i = 2; i <= N; i++) {
            for(int j = 0; j <= 9; j++) {
                // 0은 1일 경우에만 나올 수 있다.
                if(j == 0) {
                    stairs[i][0] = stairs[i - 1][1] % 1000000000;
                }
                // 9는 8일 경우에만 나올 수 있다.
                else if (j == 9) {
                    stairs[i][9] = stairs[i - 1][8] % 1000000000;
                }
                // 그 외의 경우 이전 자릿수의 양쪽의 값을 더한다.
                else {
                    stairs[i][j] = (stairs[i - 1][j - 1] + stairs[i - 1][j + 1]) % 1000000000;
                }
            }
        }

        long answer = 0;
        for(int i = 0; i <= 9; i++) {
            answer += stairs[N][i];
        }

        System.out.println(answer % 1000000000);
    }
}

• 0으로 시작하는 수는 계단수가 아니기 때문에 0을 제외한 한 자릿수를 1로 정의해준다.
• 두 자릿수부터 입력수 까지반복을 하면서 0~9의 수를 반복한다.
  • 0일 경우, 1일 경우에만 계단수가 성립하기 때문에 전 자릿수의 1의 개수를 입력한다.
  • 9일 경우, 8일 경우에만 계단수가 성립하기 때문에 전 자릿수의 8의 갯수를 입력한다.
  • 그 외의 경우, 전 자릿수의 자신 보다 1 큰 수와 작은 수를 더한 갯수를 입력한다.
  • 각 수를 입력할 때 값이 int의 크기를 벗어나지 않도록 1000000000으로 나눠준다.
• 주어진 N 자릿수의 모든 수를 더해준다. (int의 크기를 벗어날 수 있으므로 long으로 선언해 준다.)

타뷸레이션 방식을 이용해 아래의 값부터 만들어 원하는 값까지를 구해 답을 찾아내는 방법을 선택했다.
문제의 주어진 내용을 봤을 때 0으로 시작하는 수는 계단수가 아니다에서 한 자릿수의 경우 0을 제외한 수들은 다 1개씩이 있고, 두 자릿수를 예를 들어 봤을 때 9를 제외한 나머지 수들은 다 자신보다 큰 수와 작은 수로 나눠질 수 있었다. 이를 봤을 때 0과 9일 경우는 나눠 질 수 없고 하나의 경우의 수만 나오도록 생각을 했었는데, 이렇게 생각을 하면 언제 0과 9가 오는지 알 수가 없어 역으로 생각을 해서 0과 9일경우는 언제 생기는 지를 보면 1과 8일 경우에만 나올 수 가 있어 해당 규칙을 이용해서 반복문을 구현했다.
그리고 출력에서 1000000000으로 나눈 나머지를 출력한다는 건 해당 값이 일정 이상으로 올라갈 수 있다는 뜻일 수 있어 자료형을 사용하는데 잘 고려해야 된다.

 

 

문제 출처 - https://www.acmicpc.net/problem/10844