백준 15단계 (동적 계획법1)

1003번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static int[] zero_cnt = new int[41];
    public static int[] one_cnt = new int[41];
    
    public static void main(String[] args) throws IOException {    
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        init();
        
        int N = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            sb.append(zero_cnt[num] + " " + one_cnt[num] + "\n");
        }
        
        System.out.println(sb);
        
    }
    
    public static void init() {
        zero_cnt[0] = 1;
        zero_cnt[1] = 0;
        one_cnt[0] = 0;
        one_cnt[1] = 1;
        
        for(int i = 2; i < 41; i++) {
            zero_cnt[i] = zero_cnt[i-1] + zero_cnt[i-2];
            one_cnt[i] = one_cnt[i-1] + one_cnt[i-2];
        }
    }
    
}

 

 

9184번

 

 

1904번

 

 

9461번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {    
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int num = Integer.parseInt(br.readLine());
        long [] dp = new long[101];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;
        dp[4] = 2;
        
        for (int i = 5; i <= 100; i++) {
            dp[i] = dp[i-1] + dp[i-5]; 
        }
        
        for(int i = 0; i < num; i++) {
            int N = Integer.parseInt(br.readLine());
            sb.append(dp[N]).append("\n");
        }
        
        System.out.println(sb);
    }
}

 

 

1149번

 

 

1932번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {    
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader로 받은 한줄의 숫자들을 구분하기 위해서 사용
        StringTokenizer st;
        
        // 최댓값
        int max = 0;
        
        // br.readLine()은 String형이므로 int형으로 변환을 해주어야 함.
        int N = Integer.parseInt(br.readLine());
        int[][] dp = new int[N][N];
        
        // 첫번쨰 수 
        dp[0][0] = Integer.parseInt(br.readLine());
        // 두번쨰 수 ~
        for(int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j <= i; j++) {
                dp[i][j] = Integer.parseInt(st.nextToken());
                
                // 그 줄의 첫번쨰일 경우
                if(j == 0)
                    dp[i][j] += dp[i-1][j];
                // 그 줄의 마지막일 경우
                else if(j == i)
                    dp[i][j] += dp[i-1][j-1];
                else
                    dp[i][j] += Math.max(dp[i-1][j-1], dp[i-1][j]);
                
                // 최댓값 비교
                max = Math.max(max, dp[i][j]);
            }
        }
        System.out.println(max);
    }
}

 

 

2579번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {    
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        long dp[] = new long[N + 1];
        long arr[] = new long[N + 1];
        
        for(int i = 1; i <= N; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }
        
        
        if(N >= 1)
            dp[1] = arr[1];
        
        if(N >= 2)
            dp[2] = arr[1] + arr[2];
        
        for(int i = 3; i <= N; i++) {
            dp[i] = Math.max(dp[i - 2] + arr[i], dp[i-3] + arr[i-1]+arr[i]);
        }
        
        System.out.println(dp[N]);
    }
}

 

 

1463번

import java.io.*;
 
public class Main {
        static int[] min;
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        
        min = new int[num+1];
        System.out.println(dp(num));
    }
    
    private static int dp(int n) {
        if(n == 1)
            return 0;
        if (min[n] > 0)
            return min[n];
        min[n] = dp(n - 1) + 1;
        if (n % 2 == 0) {
            int tmp = dp(n / 2) + 1;
            if (min[n] > tmp)
                min[n] = tmp;
        }
        if (n % 3 == 0) {
            int tmp = dp(n / 3) + 1;
            if (min[n] > tmp)
                min[n] = tmp;
        }
        return min[n];
    }
}

 

 

10844번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    static long[][] dp;
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        dp = new long[num+1][10];
        
        for(int i = 1; i <= 9; i++) {
            dp[1][i] = 1;
        }
 
        for(int i = 2; i <= num; i++) {
            for(int j = 0; j < 10; j ++) {
                if(j == 0) dp [i][j] = (dp[i-1][j+1]) % 1000000000;            // [i][0] 일 떄는 +1만 고려
                else if(j == 9) dp[i][j] = dp[i-1][j-1] % 1000000000 ;        // [i][9] 일 떄는 -1만 고려
                else dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])% 1000000000;  // 나머지는 -1, +1 모두 고려
            }
        }
        
        long sum=0;
        for(int i=0; i<=9; i++) {
            sum +=dp[num][i];
        }
        System.out.println(sum % 1000000000);
            
    }
    
}

 

 

2156번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {    
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        int dp[] = new int[N];
        int arr[] = new int[N];
        
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        if(N >= 1)
            dp[0] = arr[0];
        
        if(N >= 2)
            dp[1] = arr[0] + arr[1];
        
        if(N >= 3)
            dp[2] = Math.max(dp[1], Math.max(dp[0] + arr[2], arr[1] + arr[2]));
        
        for(int i = 3; i < N; i++) {
            dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]));
        }
        
        System.out.println(dp[N-1]);
    }
}

 

 

11053번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 수열 크기
        int num = Integer.parseInt(br.readLine());
        
        int arr[] = new int[num];
        int dp[] = new int[num];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        dp[0] = 1;
        
        for(int i = 1; i < num; i++) {
            dp[i] = 1;
            for(int j = 0; j < i; j++) {
                if(arr[j] < arr[i] && dp[i] <= dp[j])
                    dp[i] = dp[j] + 1;
            }
        }
        
        Arrays.sort(dp);
        
        System.out.println(dp[num-1]);
        
        
    }
}

 

 

11054번

 

 

2565번

 

 

9251번

 

 

1912번

 

 

12865번