JAVA) 백준으로 공부하는 자바일기 (Dynamic Programming)

# 1로 만들기 (문제 1463번)

 1. 주석친 코드가 DP 사용 (본래 코드는 분기한정사용)

 2. DP사용한게 조건이 하나 더걸리니까 속도는 빨라졌다. (당연히 메모리는 늘었지만)

 3. 문제를 풀기 위한 코드지, 1로 만들때 사용한 경로는 저장하지 않았기에, 경로출력문제라면 큐를 쓰자

import java.util.*;

public class Main {
    static int temp = 100_000;
    static int[] visited = new int[100_000_1];

    public static int method1(int n){
        if(n%3==0) return n/3;
        return 0;
    }
    public static int method2(int n){
        if(n%2==0) return n/2;
        return 0;
    }
    public static int method3(int n){
        return n-1;
    }

    public static void dfs(int n,int cnt){
        if(n == 0) return;
        else if(cnt>temp){
            return;
        }
        else if(n==1) {
            if(temp>cnt) temp=cnt;
            return;
        }

        dfs(method1(n),cnt+1);
        dfs(method2(n),cnt+1);
        dfs(method3(n),cnt+1);

        /*if(visited[n]>cnt){
            dfs(method1(n),cnt+1);
            dfs(method2(n),cnt+1);
            dfs(method3(n),cnt+1);
            visited[n]=cnt;
        }*/
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        //Arrays.fill(visited,500);

        dfs(n,0);
        System.out.println(temp);

    }
}

---

# 1, 2, 3 더하기 (문제 9095번)

 1. DP 문제인데 자꾸 DFS.......... 

 2. 다른사람의 풀이를 봤는데, 왜 d(n) = d(n-1)+d(n-2)+d(n-3) 이 성립하는건지 이해를 못하겠다... 주륵...

import java.util.*;

public class Main {
    static int cnt=0;
    static boolean visited[] = new boolean[12];
    public static void dfs(int n){
        if(n==0) {
            cnt++;
            return;
        }else if(n<0) return;
        dfs(n-1);
        dfs(n-2);
        dfs(n-3);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        for(int i=0;i<t;i++){
            int n=sc.nextInt();
            dfs(n);
            System.out.println(cnt);
            cnt=0;
        }
        
        
    }
}

---

# 2xn 타일링

1. 점화식 찾는게 너무 어렵다.... (계속 풀어서 사고력을 기르자...)

import java.util.Scanner;

public class Main {

    static int[] d;

    //1<= n <=1000
    public static int solve(int n){
        if(d[n]!=0) return d[n];

        return d[n]=(solve(n-1)+solve(n-2))%10007;
    }

    public static void printArr(int [] arr){
        for(int i : arr){
            System.out.print(i+" ");
        }
    }

    public static void main(String[] args) {
        d= new int[1001];
        d[1]=1;
        d[2]=2;

        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();

        System.out.println(solve(n));

        //printArr(d);

    }
}