[백준 알고리즘] (DP)10844번 Java 2가지 풀이

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

알고리즘 문제풀이(PS) 시작하기

 

백준 알고리즘 10844번

 

<풀이> - Bottom up

package dp;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class N10844 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        br.close();
        
        int[][] dp = new int[101][11];
        
        for(int i =1; i<=9; i++) {
            dp[1][i] = 1; //n=1인 경우 정의
        }
        
        for(int i =2; i<=n;i++) {
            dp[i][0] = dp[i-1][1]; //n>=2인 경우 중 마지막 자리가 1인 개수
            for(int j=1; j<=9;j++) {
                dp[i][j] = (dp[i-1][j-1] +dp[i-1][j+1]) %1000000000; 
                // j=9 즉 마지막 자리가 9인 경우 [n-1][10]은 넣어주지 않았기 때문에 0이 연산된다. 
            }
        }
        long sum =0;
        for(int i=0; i<10; i++) {
            sum += dp[n][i];
        }
 
        System.out.println(sum%1000000000);
    }
 
}
 
 

 

 

<풀이> - Top Down

package dp;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class N10844_TD {
 
    public static int mod = 1000000000;
    public static long[][] dp;
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        br.close();
        
        dp = new long[n+1][10];
        long sum=0;
        
        for(int l=1; l<=9; l++) {
            sum += calculate(n, l);
        }
        System.out.println(sum%mod);
        
    }
    public static long calculate(int n, int l) {
        if(n==1) {
            return 1;
        }
        if(dp[n][l]>0) {
            return dp[n][l];
        }
        
        if(l==0) {
            dp[n][l] = calculate(n-1, 1);
        }
        else if(l==9) {
            dp[n][l] = calculate(n-1,8);
        }
        else {
            dp[n][l] = calculate(n-1, l-1) + calculate(n-1, l+1);
        }
        return dp[n][l]%mod;
    }
 
}