[Java] 백준 10844 쉬운 계단 수

10844 쉬운 계단 수 문제 링크

문제분석

• 인접한 모든 자리의 차이가 1인 수를 계단 수라고 함
  • ex) 45656
• N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하기

제약 사항

• 계단 수는 0으로 시작할 수 없음

입력 조건

• 첫째 줄 : 계단 수의 길이 N (1 ≤ N ≤ 100)

출력 조건

• 답을 1,000,000,000으로 나눈 나머지 출력

---

#1

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int N = sc.nextInt();
        int answer = 0;
        int[][] arr = new int[N][10];

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

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

        for(int i=0; i<10; i++) {
            answer += arr[N-1][i];
        }
        System.out.println(answer);

        sc.close(); // Scanner 닫기
    }
}

---

#2

• 갈수록 수가 너무 커짐
• int 자료형에 담을 수 없음

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int N = sc.nextInt();
        Long answer = 0L;
        Long[][] arr = new Long[N][10];

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

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

        for(int i=0; i<10; i++) {
            answer += arr[N-1][i];
        }
        System.out.println(answer);

        sc.close(); // Scanner 닫기
    }
}

---

#3

• Long은 참조타입임
  • 참조타입은 초기화가 null로 되기 때문에 arr[i+1][1] += arr[i][0];에서 에러 발생

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int N = sc.nextInt();
        long answer = 0L;
        long[][] arr = new long[N][10];

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

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

        for(int i=0; i<10; i++) {
            answer += arr[N-1][i];
        }
        System.out.println(answer);

        sc.close(); // Scanner 닫기
    }
}

---

#4

• 문제를 잘 읽을 수 있도록..
• 값이 너무 커서 long에도 안 들어감
• 문제가 그걸 고려해서 답을 1,000,000,000으로 나눈 나머지 출력하라고 함..

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int N = sc.nextInt();
        long mod = 1000000000;
        long answer = 0L;
        long[][] arr = new long[N][10];

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

        for(int i=0; i<N-1; i++) {
            arr[i+1][1] = (arr[i+1][1] + arr[i][0]) % mod;
            for(int j=1; j<9; j++) {
                arr[i+1][j-1] = (arr[i+1][j-1] + arr[i][j]) % mod;
                arr[i+1][j+1] = (arr[i+1][j+1] + arr[i][j]) % mod;
            }
            arr[i+1][8] = (arr[i+1][8] + arr[i][9]) % mod;
        }

        for(int i=0; i<10; i++) {
            answer += arr[N-1][i];
        }
        System.out.println(answer%mod);

        sc.close(); // Scanner 닫기
    }
}

• 성공..
  

---

again

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        long[][] arr = new long[N][10];
        arr[0][0] = 0;
        for(int i=1; i<10; i++) {
            arr[0][i] = 1;
        }

        for(int i=1; i<N; i++) {
            for(int j=0; j<10; j++) {
                if(j==0) arr[i][j+1] += arr[i-1][j]%1000000000;
                else if(j==9) arr[i][j-1] += arr[i-1][j]%1000000000;
                else {
                    arr[i][j-1] += arr[i-1][j]%1000000000;
                    arr[i][j+1] += arr[i-1][j]%1000000000;
                }
            }
        }

        long answer = 0;
        for(int i=0; i<10; i++) {
            answer += arr[N-1][i];
        }
        bw.write(answer%1000000000+"");
        bw.flush();
        bw.close();
    }
}

• 와.. 다시 풀었는데 정확히 int->long 이랑 %1000000000 때문에 다시 함..