백준 10844 쉬운 계단수

DP 2번째 문제

문제
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

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

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

위의 문제를 보면 알 수 있듯이 1만큼의 차이만 있는 수를 찾는 문제이다

문제를 읽고 잠시 생각을 해 본 결과 크게 어렵다는 생각은 들지 않았다
DP 문제라서 DP로 접근을 해보려고 했고 처음으로 나온 방법이 아래의 코드이다

public class P10844 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] DP = new int[n+1];

        DP[0] = 9;

        for(int i = 0; i < n; i++){
            DP[i + 1] = (DP[i] * 2) - (i+1);
            System.out.println(arr[i + 1]);
        }

        System.out.println(DP[n - 1] % 1000000000);
    }
}

결국 문제에서 말하는 계단 수가 되려면 그 전 자리수에서도 계단수이어야 될 수 있다
그리고 마지막이 0이나 9로 끝나는 경우에는 0 -> 1 이나 9 -> 8 인 경우 밖에 없다
다른 수 들은 1을 더하거나 뺄 수 있는데 0,9는 아니다
나는 0,9의 개수에 규칙이 있는줄 알고 나름대로의 규칙을 세워서 1차원 배열로 해결하려고 했다

그렇게 코드를 구현했는데 틀렸다!!

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

public class P10844 {
    static int modifiedNum = 1000000000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int DP[][] = new int[n + 1][11];
        int result = 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][1] % modifiedNum;
                else if (j == 9) {
                    DP[i][j] = DP[i - 1][8] % modifiedNum;
                } else
                    DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % modifiedNum;
            }
        }

        for (int i = 0; i <= 9; i++) {
            result = (result + DP[n][i]) % modifiedNum;
        }

        System.out.println(result);
    }
}

그래서 바꾼 코드

배열 DP 는 N의 수와 끝의 자리를 가진다

그러면 이제 N = 1 부터 시작해서 각 N이 몇개씩 가지는지 저장한다

그리고 예를 들어 DP[3][4]는 DP[2][3]과 DP[2][5]의 개수를 더해주면 된다
근데 이때 끝의 자리가 0 또는 9이면 한쪽밖에 더할 수 없으므로

if (j == 0)
  DP[i][j] = DP[i - 1][1] % modifiedNum;
else if (j == 9) {
  DP[i][j] = DP[i - 1][8] % modifiedNum;

이런식으로 예외 조건을 정해주면 된다!

뭔가 슬슬 이제 DP에 대한 감이 오는 것 같다
좀 더 문제를 풀어보긴 해야겠다

백준 10844 쉬운 계단 수