[백준] Silver I. 쉬운 계단 수

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

 

사용 알고리즘

 

• 다이나믹 프로그래밍

 

풀이

 

1차원 으로 생각해서 틀린 풀이

public class Main {
    static int n;
    static int [] d = new int[102];
    static int [] s = new int[102];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        d[0] = 0;
        d[1] = 9;
        s[0] = 0;
        for(int i = 2; i <= n; i++) {
            s[i] = i - 1;
            d[i] = (2 * (d[i-1] - 1) + s[i]) % 1000000000;
        }

        System.out.println(d[n]);
    }
}

 

 

정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
    테이블: d[i][j]: 길이가 i고 마지막 자릿수가 j인 계단의 수
    점화식: d[i][j] = d[i-1][j-1] + d[i-1][j+1]
 */
public class Main {
    static int n;
        static int [][] d = new int[102][10];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        for(int i = 1; i <= 9; i++) {
            d[1][i] = 1;
        }

        for(int i = 2; i <= n; i++){
            for(int j = 0; j <= 9; j++) {
                if (j > 0) d[i][j] += d[i-1][j-1]; // j가 9일때 edge case 처리
                if (j < 9) d[i][j] += d[i-1][j+1]; // j가 0일때 edge case 처리
                d[i][j] %= 1000000000;
            }
        }

        long res = 0;
        for(int i = 0; i <= 9; i++) {
            res += d[n][i];
            res %= 1000000000;
        }
        System.out.println(res);
    }
}

 

 

회고

 

테이블

• d[i][j]: 길이가 1고 마지막 자릿수가 j인 계단의 총합

점화식

• d[i][j] = d[i-1][j-1] + d[i-1][j+1], 단 i,j는 유효 범위 내여야 함.

n = 2일때

d[2][0] = d[1][1] // 예외처리
d[2][1] = d[1][0] + d[1][2]
d[2][2] = d[1][1] + d[1][3]
d[2][3] = d[1][2] + d[1][4]
d[2][4] = d[1][3] + d[1][5]
d[2][5] = d[1][4] + d[1][6]
d[2][6] = d[1][5] + d[1][7]
d[2][8] = d[1][7] + d[1][9]
d[2][9] = d[1][8] // 예외처리

 

n = 3일떄

d[3][0] = d[2][1]
d[3][1] = d[2][0] + d[2][2]
...
d[3][9] = d[2][8]

 

이런 규칙으로 이어지게 된다.

 

맨 처음에 n = 1일떄 초기화를 해주어야 하므로,

for(int i = 1; i <= 9; i++) {
    d[1][i] = 1;
}

 

이렇게 값을 1로 할당해준다.

 

for(int i = 2; i <= n; i++){
    for(int j = 0; j <= 9; j++) {
        if (j > 0) d[i][j] += d[i-1][j-1]; // j가 9일때 edge case 처리
        if (j < 9) d[i][j] += d[i-1][j+1]; // j가 0일때 edge case 처리
        d[i][j] %= 1000000000;
    }
}

 

그리고, 해당 자릿수에 맞는 값을 업데이트 해주는데 범위를 조심해야 한다. d[i][-1]이나 d[i][10]은 제외해야 하므로, 두가지 케이스를 예외처리 해준다.

 

long res = 0;
for(int i = 0; i <= 9; i++) {
    res += d[n][i];
    res %= 1000000000;
}
System.out.println(res);

 

그리고, 마지막에 모든 값을 더해주면 끝난다.

 

음.. 일단 계속 풀어봐야겠다