[백준] 쉬운 계단 수 - 자바

 

N = 1일 때

'0으로 시작하는 수는 계단수가 아니다.' 라는 조건으로 인해

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

끝나는 수	0	1	2	3	4	5	6	7	8	9
N=1	0	1	1	1	1	1	1	1	1	1

 

 

N = 2일 때

0은 1에서 올 수 있음  dp[2][0] = dp[1][1]  →  dp[i][j] = dp[i-1][1]

(0에서 시작은 안 되지만 중간에 낄 수 있음)

끝나는 수	0	1	2	3	4	5	6	7	8	9
N=1	0	1	1	1	1	1	1	1	1	1
N=2	1

 

 

9는 8에서 올 수 있음  dp[2][9] = dp[1][8]  →  dp[i][j] = dp[i-1][8]

 (다음 칸이 없으므로 내려오는 경우는 불가)

끝나는 수	0	1	2	3	4	5	6	7	8	9
N=1	0	1	1	1	1	1	1	1	1	1
N=2	1									1

 

 

나머지는 한 칸 아래, 한 칸 위에서 올 수 있음

예시 ) 2는 1, 3에서 올 수 있음  dp[2][2] = dp[1][1] + dp[1][3] →  dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

끝나는 수	0	1	2	3	4	5	6	7	8	9
N=1	0	1	1	1	1	1	1	1	1	1
N=2	1		2							1

 

예시 ) 1은 2에서 올 수 있음 (0에서 시작이 불가하므로 0에서 오는 경우는 불가) dp[2][1] = dp[1][2]

하지만 이전의 0으로 끝나는 경우가 없으므로 dp[2][1] =dp[1][2] + dp[1][0]으로 표현 가능하다.

→  dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

끝나는 수	0	1	2	3	4	5	6	7	8	9
N=1	0	1	1	1	1	1	1	1	1	1
N=2	1	1	2							1

 

N = 3일 때

따라서 마찬가지로 구할 수 있음

0은 1에서 올 수 있음  dp[3][0] = dp[2][1]  →  dp[i][j] = dp[i-1][1]

9는 8에서 올 수 있음  dp[3][9] = dp[2][8]  →  dp[i][j] = dp[i-1][8]

 

나머지는 한 칸 아래, 한 칸 위에서 올 수 있음

예시 ) 1은 2, 0에서 올 수 있음(0에서 시작은 안 되지만 중간에 낄 수 있음)

dp[3][1] = dp[2][0] + dp[2][2]→dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1]

 

 

풀이

계단 도착 방법의 수를 저장할 배열을 선언한 후 dp[1]의 0번째 빼고는 1로 초기화

int 범위를 넘을 수 있으므로 long 배열로 선언하였다.

long[][] dp = new long[N+1][10];
dp[1] = new long[] {0, 1, 1, 1, 1, 1, 1, 1, 1, 1};

 

2부터는

j가 0이면 1에서 오는 방법을

j가 9이면 8에서 오는 방법을

둘 다 아니면 j-1, j+1 방법을 더하여 저장한다.

더한 후 범위를 넘어가지 않도록 % 1000000000하여 저장하였다.

j가 0 또는 9일 때는 이미 % 1000000000한 값을 가져오므로 그냥 저장하였다.

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

 

i = N일 때 각각 j의 수로 도착하는 경우를 더하여 출력한다.

더하는 경우 int 범위를 넘을 수 있으므로 long 으로 저장하여 출력하였다.

더한 값도 범위를 넘어가지 않도록 % 1000000000하여 출력하였다.

long sum = 0;
for (int j = 0; j <= 9; j++) {
    sum += dp[N][j];
}
System.out.println(sum % 1000000000);

 

 

import java.io.*;

public class Main {
    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];
        dp[1] = new long[] {0, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        for (int i = 2; i <= N; i++) {
            for (int j = 0; j <= 9; j++) {
                if (j == 0) dp[i][j] = dp[i-1][1];
                else if (j == 9) dp[i][j] = dp[i-1][8];
                else dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;
            }
        }
        long sum = 0;
        for (int j = 0; j <= 9; j++) {
            sum += dp[N][j];
        }
        System.out.println(sum % 1000000000);
    }
}