[백준 알고리즘] (DP) 9095번 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) 시작하기

 

백준 알고리즘 9095번

 

hange Nxxxx -> Main && remove package lines!!!

이클립스에서 작성하면서 문제 이름으로 클래스를 생성하여 풀었기 때문에

클래스 이름을 Main으로 바꾸고, package 부분도 지우고 제출해야 정상적으로 돌아갑니다.

 

<풀이> - Bottom up

package dp;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class N9095 { //Bottom up
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testn = Integer.parseInt(br.readLine());
        int d[] = new int[11];
        
        d[0] = 0;
        d[1] = 1;
        d[2] = 2;
        d[3] = 4;
        
 
        for(int i=0; i<testn; i++) {
            int n = Integer.parseInt(br.readLine());
            for(int j=4; j<n+1; j++) {
                d[j] = d[j-1] +d[j-2] +d[j-3];
            }
            System.out.println(d[n]);
        }
    }
 
}
 

 

 

<풀이> - Top down

package dp;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class N9095_TD {
 
    static int[] d;
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testn = Integer.parseInt(br.readLine());
        d = new int[11];
        for(int i=0; i<testn;i++) {
            int n = Integer.parseInt(br.readLine());
            d[i] = calculate(n);
            System.out.println(d[i]);
        }
        
        
        
    }
    public static int calculate(int n) {
        if(n==1) return 1;
        else if(n==2) return 2;
        else if(n==3) return 4;
        else {
            d[n] = calculate(n-1) +calculate(n-2)+ calculate(n-3);
            
            return d[n];
        }
    }
 
}