백준11726번 문제

2 x n 타일링

bottom-up 방식

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+2];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2])%10007;
        }
        System.out.println(dp[n]%10007);
    }
}

dp배열의 1번과 2번을 각각 1과 2로 설정했다.
그 후 그림을 그려 나가며 문제를 풀다보닏 해당 문제가 피보나치 수열을 띄고 있다는 것을 알게 됐고, 다음 for문을 통해 피보나치 함수를 bottom-up 방식으로 구현했다.

다음은 top-down 방식으로 문제를 풀었다.

package DynamicPrograming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_1463 {
    public static int dp[];
    public static void main(String[] argv) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        dp=new int[N+1]; //초기값 0
        System.out.println(Dynamic(N));

    }
    public static int Dynamic(int N){
        if(N==1) return 0;
        if(dp[N]>0) return dp[N];
        dp[N] = Dynamic(N-1)+1;
        if(N%3==0) dp[N] = Math.min(dp[N],Dynamic(N/3) +1);
        if(N%2==0) dp[N] = Math.min(dp[N],Dynamic(N/2) +1);
        return dp[N];

    }

}