21.09.23 기록

백준 알고리즘 10844 풀이

🎆나의 오답

-dp 로직은 떠오르지 않아서 아래처럼 끄적이다가 해설을 봤다.

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

public class B10844 {
    public static int[] res = new int[100+1];
    public static int N;
    public static int end;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        int start = 1;
        for(int i = 1; i < N; i++) {
            start *= 10;
        }
        end = start*10;

        System.out.println(find(start));
    }
    public static int find(int start) {
        int cnt = 0;

        for(int i = start; i < start*10; i++) {
            boolean isValue = true;
            String numStr = String.valueOf(i);

            for(int j = 0; j < numStr.length()-1; j++) {
                int d = numStr.charAt(j) - numStr.charAt(j+1);

                if(d != -1 && d != 1) {
                    isValue = false;
                    break;
                }
            }

            if(isValue) { cnt++; }
        }
        return cnt;
    }
}

🎆해설(메모리 14.2MB, 시간 140ms로 통과)

-해설을 분석해봐도 뭔가 알 것 같으면서.. 모르겠는 느낌이었다. (== 이해 못했다..🙄)

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

public class Main {
    public static Long[][] dp;
    public static int N;
    public static final long MOD = 1_000_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new Long[N+1][10];

        for(int i = 0; i < 10; i++) {
            dp[1][i] = 1L;
        }

        long result = 0;
        for(int i = 1; i <= 9; i++) {
            result += find(N, i);
        }
        System.out.println(result % MOD);
    }

    public static long find(int digit, int val) {
        if(digit == 1) {
            return dp[digit][val];
        }

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

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

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

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