[백준 알고리즘] (DP) 11057번 Java 풀이

 

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) 시작하기

 

백준 알고리즘 11057번

 

<풀이> - Bottom up

package dp;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class N11057 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        int dp[][] = new int[n+1][10];
        
        for(int i =0; i<10; i++) {
            dp[1][i] = 1;
        }
        
        for(int i=2; i<=n;i++) {
            for(int j=0; j<=9; j++) {
                for(int k=0; k<=j; k++) {
                    dp[i][j] += dp[i-1][k];
                    dp[i][j] %= 10007;
                }
            }
        }
        
        int sum =0;
        for(int i =0; i<10; i++) {
            sum+=dp[n][i];
        }
        System.out.println(sum%10007);
    }
 
}