[BJ] 백준 10844 쉬운 계단 수 (JAVA)

문제

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

 

풀이 방법

dp를 사용하는 문제다. dp는 왜 항상 해도해도 새로울까...
인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다.
N이 주어지고 N자리 숫자에서 계단수가 총 몇개 있는지 구하면 되는 문제이다.
dp는 2차원 배열로 선언해주고, dp[N][m] : N자리 숫자이고 마지막 자리의 수가 m인 숫자의 개수를 넣어준다고 생각하면 된다.
그래서 반복문 N번 돌면서 j : 0부터 10까지 반복문을 돌린다.
j는 마지막 자리 숫자이다. 만약 2343라는 수는 dp[4][3]에 포함이 되는 숫자이다.
어쨌든 반복문을 돌면서 마지막 자리수에 -1, +1을 하는 경우가 0~9사이에 존재한다면 [n+1][j+1]  또는      [n+1][j-1]번째 자리에다가 현재의 값과 기존에 이미 존재하는 값을 더해서 새롭게 값을 넣어준다.
또한 수가 너무 커질 수 있으므로 dp에 넣어주기 전에 미리 1000000000을 나눠서 넣어준다.
마지막에는 dp[N][] 인 경우를 모두 더해서 출력해준다. 

 

제출 코드

import java.io.*;
import java.util.*;
public class BJ_10844_쉬운계단수 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		long [][] dp = new long[N+1][10];
		//한자리 수 인 경우
		for (int i = 1; i < 10; i++) {
			dp[1][i] = 1;
		}
		for (int i = 1; i < N; i++) {
			for (int j = 0; j <10; j++) {
				if(dp[i][j] >0) { //수가 존재하면
					if(j-1>=0 ) dp[i+1][j-1]=(dp[i+1][j-1] +dp[i][j]) %1000000000;
					if(j+1<=9) dp[i+1][j+1] =(dp[i+1][j+1] +dp[i][j])%1000000000;
				}
			}
		}
		
		long sum =0; 
		for (int i = 0; i < 10; i++) {
			sum+= (dp[N][i] % 1000000000);
		}
		System.out.println(sum % 1000000000);
	}
}