134. 10844(쉬운 계단 수)

import java.util.*;

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

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

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

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

				else if (j == 9) {
					dp[i][j] = dp[i - 1][8] % 1000000000;
				}

				else {
					dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
				}
			}
		}

		for (Long val : dp[N - 1]) {
			sum += val;
		}

		System.out.println(sum % 1000000000);
	}
}

문제요약

서로 1씩 차이가 나는 수를 계단수라고 함. 

길이 N이 주어졌을 때 계단수의 개수에 1000000000 을 나눈 나머지는 몇인가?

(ex 길이 1 => 1 2 3 4 5 6 7 8 9 길이 2 => 01 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98)

설명

길이가 2로 들어왔다고 가정해보자.

십의 자리 수에서 계단수는 01,10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98이다.

하지만 01은 십의자리 수가 아니므로 개수에서 빼준다.

그림을 그리면 다음과 같다.

이런식으로 계속 나아가면 된다.

예를들어 길이가 3이 들어왔으면,

다음과 같이 진행된다.

for i in range(1,10):
    dp[1][i] = 1

index가 0인 경우 모두 1이기 때문에 다음과 같이 1로 초기화 해준다.

0으로 시작하는 수는 계단수가 아니기 때문에 0에는 1로 초기화 하지 않는다.

 

for i in range(2,N+1):
    for j in range(10):
        if j == 0 :
            dp[i][j] = dp[i-1][1]
        elif j == 9:
            dp[i][j] = dp[i-1][8]
        else :
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

dp[인덱스][0~9] 로 생각하면 쉽다.

j = 0일때 => 0인 경우 1 값이 해당된다.

j = 9일때 => 9인 경우 8 값이 해당된다.

두 경우를 제외하고는 [이전 인덱스][자신의 수 -1] + [이전 인덱스][자신의 수 +1] 이 dp에 저장되게 된다.