백준 10844번 : 쉬운 계단 자바

 

 

 

 

✔️ 출처

쉬운 계단 수 실버 1

 

📖 문제

중복 연산이 많이 일어나고 반복적이다. 

 

이참에 다시 학교에서 배운 DP의 적용 요건을 복습하겠다. 

 

1. 최적 부분구조(Optimal substructure)
   • 큰 문제의 최적 해에 하위 문제의 최적 해가 포함
2. 하위 문제들의 중복 (overlapping recursive calls)
   • 재귀적 해법으로 풀면 같은 하위 문제에 대한 호출이 심하게 중복

 

재귀적으로 깊이만큼 0~9까지 +1 -1을 하면서 생성하다보면 엄청난 중복이 생김

이전의 깊이에서 얻은 갯수를 재활용할 수 있을 것 같음.

 

DP를 적용해보자

 

우선 0과 9는 1가지 밖에 없다.

0 → 1

9 → 8

따라서 0 과 9는 따로 처리하고 

1~8까지는 -1 +1 숫자가 계단 수이니 이전 깊이의 -1 +1 숫자의 개수를 더한다. 

 

표를 보고 직접 계단 수를 써보면 이해하기 쉽다.

 

수 \ 깊이	1	2	3	4
0	0	1 (1 → 0 )	1 (1 → 0 )	3 (1 → 0 ) * 3
1	1	1 (2 → 1, 처음 0 시작은 불가능)	3 (0 → 1, (2 → 1) * 2)	4
2	1	2	3 ( 1 →2, (3 → 2) * 2)	7 (3  → 2) * 3 ,     (4  → 3) * 4

 

---

🔅 문제 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        long[][] dp = new long[n+1][10];

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

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= 8; j++) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] % 1000000000;
            }

            // 0과 9 따로 처리
            dp[i][0] = dp[i - 1][1] ;
            dp[i][9] = dp[i - 1][8] ;
        }
        
        long sum  = 0;
        for (int i = 0; i < 10; i++) {
            sum += dp[n][i];
            sum %= 1000000000;
        }

        bw.write(sum + "");
        bw.flush();
        bw.close();
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  딱 봐도 매우매우 큰 숫자가 연산되고, 아무리 큰 수로 나눈다 하더라도 int 형을 넘어갈 수도 있기에 되도록 long타입을 주자.