[백준/JAVA] 10844번: 쉬운 계단 수

🔺 문제

10844번: 쉬운 계단 수

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static long mod = 1000000000;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        long[][] D = new long[N + 1][11];
        
        // 길이가 1일 때 만드는 높이 i로 끝나는 계단 수의 모든 경우의 수
        for(int i = 1 ; i <= 9 ; i++) {
            D[1][i] = 1;
        }
        
        for(int i = 2 ; i <= N ; i++) {
            D[i][0] = D[i-1][1];    // 높이가 0이면 바로 앞 단계가 1이어야 올 수 있음
            D[i][9] = D[i-1][8];    // 높이가 9면   바로 앞 단계가 8이어야 올 수 있음
            
            // 높이가 1~8이면 자신보다 한 단계 위 아래 모두에서 올 수 있음
            for(int j = 1 ; j <= 8 ; j++) {
                D[i][j] = (D[i-1][j-1] + D[i-1][j+1]) % mod;
            }
        }
        
        long sum = 0;
        for(int i = 0 ; i < 10 ; i++) {
            sum = (sum + D[N][i]) % mod;
        }
        System.out.println(sum);
    }
}

✅ 해결 아이디어
✔ DP - 점화식
→ D[N][H] : 길이가 N인 계단에서 높이 H로 종료되는 계단 수를 만들 수 있는 경우의 수
    (높이에 따라 다른 점화식)

 

---

🔺 다른 풀이들

- Top-Down 방식도 올려놓으심

[백준] 10844번 : 쉬운 계단 수 - JAVA [자바]

 

 

 

- 상세한 설명

백준 10844번 (DP) - 쉬운 계단 수 (JAVA) 문제 풀이

[백준/10844/Java] 쉬운계단수

---

💬 느낀 점

2차원 배열...... 점화식을 구하는 것은 익숙하지 않은 듯허다...

DP 과정 따르면서 점화식을 잘 찾아봐야디,,,

 

 

1회독	2회독	3회독	4회독	5회독
V	7/6

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편