[백준] 동적계획법 (10844 : 쉬운 계단 수)

문제

---

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

10844번: 쉬운 계단 수

---

해설

---

해당 문제는 표를 조금만 그려봐도 부분 문제를 확인할 수 있다.

N = 1	N = 2	N = 3
1	0	1
	2	1
		3
2	1	0
		2
	3	2
		3
생략
8	7	6
		8
	9	8
9	8	7
		9

위의 표를 확인해보면

1로 시작하는 수는 다음 수로 0, 2

2로 시작하는 수는 다음 수로 1, 3이 가능한 것을 확인할 수 있다.

이는 즉, N으로 시작하는 수는 다음수로 N-1, N+1을 가질 수 있음을 의미한다.

여기서 주의해야할 점은 0과 9의 다음 수로 올 수 있는 경우는 각각 1과 8밖에 없음을 인지해야 한다!.

따라서 이를 동적 계획법으로 해결한 코드는 아래와 같다.

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();

    static long num[][];

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        num = new long[N+1][10];

        long res = 0;

        for (int i = 1; i < 10; i++) {
            res += dp10844(N, i);
        }
        sb.append(res % 1000000000).append("\n");
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static long dp10844(int len, int idx) {
        if(idx < 0 || idx > 9){
            return 0;
        }
        if(len == 1){
            return num[len][idx] = 1;
        }
        if(num[len][idx] == 0){
            num[len][idx] = (dp10844(len-1, idx-1) % 1000000000)
                    + (dp10844(len-1, idx+1) % 1000000000);
        }
        return num[len][idx] % 1000000000;
    }
}

 

 

재귀함수를 이용하는 Top-Down 방식이다.

---

1. 아직 값이 구해지지 않은 경우, 재귀함수를 통해 부분 문제로 분할해준다.
2. 2차원 배열의 행은(len) 계단수의 길이를 의미하며, 계단수 길이가 1이면 1~9까지 각각 1개씩만을 가질 수 있다.
   따라서 이를 가장 작은 문제로 설정한다.
3. 이후, 2자리 이상의 계단수는 앞의 표에서 본 것 처럼 0과 9가 아닌 경우에는 N-1, N+1을 다음 수로 가질 수 있다.
   이를 2차원 배열의 열(idx)를 통해 구현하였다.
4. 문제의 조건처럼 1000000000으로 나눈 나머지를 출력한다.
   (수가 너무 커서 모든 부분에 나머지 연산을 해주지 않으면 오버플로우가 발생하여 값이 제대로 나오지 않는다.)

---

결론

---

요즘 뭔가 문제가 잘풀리는 느낌?!?

추석내내 코로나 때문에 고생하고 쉬다가 오랜만에 블로그에 글을 쓰는 것 같당.

앞으로 다시 열심히 써야지~!

---