백준 10844 쉬운 계단 수 - JAVA

10844 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

<Top-Down>

import java.io.*;
import java.util.*;
 
public class Main{
    static long[][] dp;
    static long num;
    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());
        dp = new long[N+1][10];
        num = 1000000000;
        
        for(int i = 1; i < 10; i++) {
            dp[1][i] = 1;
        }
 
        long ans = 0;
        for (int i = 0; i <= 9; i++) {
            ans = (ans + stairCount(N, i)) % num;
        } 
        bw.write(String.valueOf(ans));
        bw.flush();
    }
    
    private static long stairCount(int N, int val) {
        if (N == 1) {
            return dp[N][val];
        }
        
        if (dp[N][val] == 0) {
            long result = 0;
            
            if(val > 0) {
                result += stairCount(N-1, val-1);
            }
            if (val < 9) {
                result += stairCount(N-1, val+1);
            }
            
            result %= num;
            dp[N][val] = result;
            
            return result;
        }
        return dp[N][val];
    }
}

 
<Bottom-Up>

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];
        long num = 1000000000;
        
        for(int i = 1; i < 10; i++) {
            dp[1][i] = 1;
        }
 
        for (int i = 2; i <= N; i++) {
            for(int j = 0; j <= 9; j++) {
                if (j > 0) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % num;
                }
                if (j < 9) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % num;
                }
                dp[i][j] %= num;
            }
        }
        long result = 0;
        for (int i = 0; i <= 9; i++) {
            result = (result + dp[N][i]) % num;
        }
        bw.write(String.valueOf(result));
        bw.flush();
    }
}

 

알고리즘 설명

---

개인적으로 이번 문제는 감이 좋은 편이라면, 빠르게 풀었을 것이라고 생각합니다. 저도 머리로만 풀다가 답답해서 노트에 2차원 배열을 적다보니 공식이 보인 문제입니다. 기준은 마지막 자릿수로 0부터 9까지 배열을 N+1개 생성하고(1-base-position), 마지막 숫자가

1. 0이라면
   dp[N][val]의 값은 dp[N-1][val + 1]
2. 1~8이라면
   dp[N][val]의 값은 dp[N-1][val-1] + dp[N-1][val+1]
3. 9 라면
   dp[N][val]의 값은 dp[N-1][val-1]

이 공식을 조건문으로 푼다면, N이 0보다 클 경우에는 dp[N-1][val + 1]의 값을 result 변수에 저장하고, N이 9보다 작은 경우에는 dp[N-1][val-1]값을 result에 더한다면 쉽게 코드를 채워 나갈 수 있을것이라 생각합니다. 수학을 공부하는게 아닌만큼 적으면서 푼다는게 절대 부끄러운일이 아니라고 생각합니다. 저도 배열을 노트에 채워적다가 발견했습니다. ㅎㅎ...
배열을 채워넣는 방식은 Top-Down 방식을 사용했습니다. 재귀가 처음에는 로직을 이해하기 어렵지만 보면 볼 수록 참 매력있는 구조인것 같습니다. 물론 Bottom-Up방식으로도 해결 가능합니다. Bottom-up 코드도 보고 가시면 좋을 것 같습니다. 어떤 방식이 적합한지는 문제와 상황에 따라 적절한 방법을 선택하시기 바랍니다. dp는 확실히 많은 예제를 풀어보고 익숙해지는 것이 중요한 것 같습니다.

 

코드 해석

---

주의할 점은 반복문안에 result를 선언해서, 배열에 result를 저장하고 나면 result가 초기화 되어야 한다는 점입니다. result의 위치를 주의하여 푼다면 문제는 없을 것 같습니다. N의 값이 1인 경우, 0은 0, 1부터 9까지는 1로 채워넣고, N > 0과 N < 9에 맞는 재귀함수를 호출해 주어 배열에 값을 채워넣고, 함수 스택이 종료되면, 해당 dp[N]의 배열을 반복문으로 ans라는 변수에 누적합해주어 출력합니다.