Java 백준 10844 쉬운 계단 수

백준 링크

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

10844번: 쉬운 계단 수

---

문제

입력

출력

입출력 예시

---

제출한 코드

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static long[][] dp;
	static int n;

	public static void main(String[] args) throws Exception {
		init();
		run();
	}

	private static void init() throws Exception {
		n = Integer.parseInt(br.readLine());
		dp = new long[n + 1][10];
	}

	private static void run() {
		// 기본 값 세팅
		for (int i = 1; i < 10; i++) {
			dp[1][i] = 1;
		}

		// n번째 자리까지 계산.
		for (int i = 2; i <= n; i++) {
			// 0 ~ 9 경우의 수 계산
			for (int j = 0; j < 10; j++) {
				// 0이 가능한 경우 = 앞자리 수가 1인 경우
				if (j == 0) {
					dp[i][0] = dp[i - 1][1] % 1000000000;
				}
				// 9가 가능한 경우 = 앞자리가 8인 경우
				else if (j == 9) {
					dp[i][9] = dp[i - 1][8] % 1000000000;
				} 
                // 나머지 경우
                else {
					dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
				}
			}

		}
        
        // 정답 출력
		long answer = 0;
		for (int i = 0; i < 10; i++) {
			answer += dp[n][i];
		}
		System.out.println(answer % 1000000000);
	}
}

 

1. 출력 조건에 적힌 1,000,000,000으로 나눈 값을 출력하라는 메세지에서 int타입으로는 부족하단 것을 확인하고 long 타입으로 진행한다.

2. 자리수와 0~9까지 확인하기 위해 2차원 배열을 사용하고 1자리 수인 경우를 기본 값으로 세팅한다.

3. +1 or -1 인 경우를 확인하기에 0 or 9가 올 수 잇는 경우에 대해서 따로 처리해준다.

4. 나머지 경우에서는 -1과 +1인 경우의 수를 더해준다.

5. 출력시 N자리 값에 대해 가능한 모든 경우의 수를 더하고 1,000,000,000으로 나눠준다.