CT

[BOJ] 22단계 동적 계획법 1

kinggora 2023. 4. 20. 00:22
1 24416 알고리즘 수업 - 피보나치 수 1 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    private static int[] f;
    private static int rc = 0;
    private static int dp = 0;


    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        fib(N);
        f = new int[N + 1];
        fibonacci(N);
        System.out.println(rc + " " + dp);

    }

    //피보나치 수 - 재귀 호출
    public static int fib(int n) {
        if (n == 1 || n == 2) {
            rc++;
            return 1;
        }
        return fib(n-1) + fib(n-2);
    }

    //피보나치 수 - 동적 프로그래밍
    public static int fibonacci(int n) {
        f[1] = f[2] = 1;
        for(int i = 3; i <= n; i++) {
            f[i] = f[i-1] + f[i-2];
            dp++;
        }
        return f[n];
    }
}

 

2 9184 신나는 함수 실행 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private static int[][][] dp = new int[21][21][21];


    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        initDp();
        while(true) {
            String input = reader.readLine();
            if(input.equals("-1 -1 -1")) {
                break;
            }
            StringTokenizer tokenizer = new StringTokenizer(input);
            int a = Integer.parseInt(tokenizer.nextToken());
            int b = Integer.parseInt(tokenizer.nextToken());
            int c = Integer.parseInt(tokenizer.nextToken());
            sb.append(String.format("w(%d, %d, %d) = %d\n", a, b, c, getDp(a,b,c)));
        }
        System.out.print(sb);
    }

    public static void initDp() {
        for(int i = 0; i <= 20; i++) {
            for(int j = 0; j <= 20; j++) {
                for(int k = 0; k <= 20; k++) {
                    if(i == 0 || j == 0 || k == 0) {
                        dp[i][j][k] = 1;
                    } else if(i < j && j < k){
                        dp[i][j][k] = dp[i][j][k-1] + dp[i][j-1][k-1] - dp[i][j-1][k];
                    } else {
                        dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k] + dp[i-1][j][k-1] - dp[i-1][j-1][k-1];
                    }
                }
            }
        }
    }

    public static int getDp(int a, int b, int c) {
        if(a <= 0 || b <= 0 || c <= 0) {
            return dp[0][0][0];
        } else if(a > 20 || b > 20 || c > 20) {
            return dp[20][20][20];
        } else {
            return dp[a][b][c];
        }
    }
}

 

3 1904 01타일

1 ≤ N ≤ 1,000,000

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        //00 타일의 개수: 0~n개
        //1 타일의 개수: N-2n개
        int[][] dp = generateDp(N + 1);
        int count = 0;
        int n = N / 2;
        for(int i = 0; i <= n; i++) {
            int j = N - 2 * i;
            if(i > j) {
                count += dp[i+1][j];
            } else {
                count += dp[j+1][i];
            }
        }
        System.out.println(count % 15746);
    }

    public static int[][] generateDp(int max) {
        int[][] dp = new int[max+1][max+1];
        for(int i = 0; i <= max; i++) {
            dp[i][0] = 1;
            dp[i][i] = 1;
            for(int j = 1; j < i; j++) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }
        }
        return dp;
    }

}

*조합법 사용: 메모리 초과

 

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

public class Main {
    private static int[] tile = new int[2];
    private static int count = 0;


    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        //00 타일의 개수: 0~n개
        //1 타일의 개수: N-2n개
        tile[0] = 1; //'1' 타일의 길이
        tile[1] = 2; //'00' 타일의 길이
        dp(N);
        System.out.println(count % 15746);

    }

    public static void dp(int n) {
        if(n == 0 || n == 1) {
            count++;
            return;
        }
        for(int i = 0; i < 2; i++) {
            dp(n - tile[i]);
        }
    }

}

*백트래킹 사용: 시간 초과

 

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

public class Main {

    private static int[] f;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        f = new int[N + 1];
        //1 2 3 5 8 13...
        System.out.println(fibonacci(N));
    }

    public static int fibonacci(int n) {
        f[0] = f[1] = 1;
        for(int i = 2; i <= n; i++) {
            f[i] = (f[i-1] + f[i-2]) % 15746;
        }
        return f[n];
    }
}

*결과값이 피보나치 수와 같음을 유추함

 

4 9461 파도반 수열

피보나치 수와 비슷한 규칙

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

public class Main {
    
    private static final int MAX = 100;
    private static long[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());
        dp = new long[MAX+1];
        dp[1] = dp[2] = dp[3] = 1;
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < T; i++) {
            int N = Integer.parseInt(reader.readLine());
            sb.append(padovan(N)).append("\n");
        }
        System.out.print(sb);
    }

    public static long padovan(int n) {
        if(dp[n] != 0) {
            return dp[n];
        }
        return dp[n] = padovan(n-2) + padovan(n-3);
    }
}

 

5 1912 연속합 
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 reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for(int i = 0; i < N; i++) {
            int num = Integer.parseInt(tokenizer.nextToken());
            sum += num;
            if(max < sum) {
                max = sum;
            }
            if(sum < 0) {
                sum = 0;
            }
        }
        System.out.print(max);
    }
}

 

6 1149 RGB거리

i번째 집을 각각의 색으로 칠할 때, 1~i번째 집을 모두 칠하는 최소 비용으로 부분문제를 정의

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

public class Main {
    private static final int RED = 0;
    private static final int GREEN = 1;
    private static final int BLUE = 2;
    private static int[][] dp;
    private static int[][] cost;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());
        cost = new int[T][3];
        dp = new int[T][3];
        for(int i = 0; i < T; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            cost[i][RED] = Integer.parseInt(tokenizer.nextToken());
            cost[i][GREEN] = Integer.parseInt(tokenizer.nextToken());
            cost[i][BLUE] = Integer.parseInt(tokenizer.nextToken());
        }

        dp[0][RED] = cost[0][RED];
        dp[0][GREEN] = cost[0][GREEN];
        dp[0][BLUE] = cost[0][BLUE];
        
        System.out.println(Math.min(dp(T-1, RED), Math.min(dp(T-1, GREEN), dp(T-1, BLUE))));
    }

    public static int dp(int n, int color) {
        if(dp[n][color] == 0) {
            if(color == RED) {
                dp[n][color] = Math.min(dp(n-1, GREEN), dp(n-1, BLUE)) + cost[n][RED];
            } else if(color == GREEN) {
                dp[n][color] = Math.min(dp(n-1, RED), dp(n-1, BLUE)) + cost[n][GREEN];
            } else {
                dp[n][color] = Math.min(dp(n-1, RED), dp(n-1, GREEN)) + cost[n][BLUE];
            }
        }
        return dp[n][color];
    }
}

*단순히 RGB 중 최소값을 더하는 것이 아닌 모든 경우의 수에서 누적합이 최소인 것을 구해야 한다.

*예를 들어 i번째로 R색을 칠할 때 i-1번째 색은 G나 B이고 1~i-1번째까지의 누적합이 더 적어야 한다.

 

7 1932 정수 삼각형

각 층의 모든 칸마다 최댓값을 저장하면서 동적 계획법으로 푸는 문제

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

public class Main {
    private static Integer[][] dp;
    private static int[][] num;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());
        num = new int[T][];
        dp = new Integer[T][];
        for(int i = 0; i < T; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            num[i] = new int[i+1];
            dp[i] = new Integer[i+1];
            for(int j = 0; j < i + 1; j++) {
                num[i][j] = Integer.parseInt(tokenizer.nextToken());
            }
        }
        dp[0][0] = num[0][0];

        int max = Integer.MIN_VALUE;
        for(int i = 0; i < T; i++) {
            if(dp(T-1, i) > max) {
                max = dp(T-1, i);
            }
        }
        System.out.println(max);
    }

    public static int dp(int depth, int idx) {
        if(dp[depth][idx] == null) {
            if(idx == 0) {
                dp[depth][idx] = dp(depth-1, idx) + num[depth][idx];
            } else if(idx == depth) {
                dp[depth][idx] = dp(depth-1, idx-1) + num[depth][idx];
            } else {
                dp[depth][idx] = Math.max(dp(depth-1, idx-1), dp(depth-1, idx)) + num[depth][idx];
            }
        }
        return dp[depth][idx];
    }
}

*정수의 범위가 0~9999이기 때문에 dp용으로 Integer 배열을 사용하였다.

 

8 2579 계단 오르기
  1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
  2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
  3. 마지막 도착 계단은 반드시 밟아야 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    private static int[] num;
    private static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());
        num = new int[T];
        dp = new int[T];

        for(int i = 0; i < T; i++) {
            num[i] = Integer.parseInt(reader.readLine());
        }
        System.out.println(dp(T-1));
    }

    public static int dp(int idx) {
        if(dp[idx] == 0) {
            if(idx == 0) {
                dp[idx] = num[0];
            } else if(idx == 1) {
                dp[idx] = num[0] + num[1];
            } else if(idx == 2) {
                dp[idx] = Math.max(num[0], num[1]) + num[2];
            } else {
                dp[idx] = Math.max(dp(idx-3) + num[idx-1], dp(idx-2)) + num[idx];
            }
        }
        return dp[idx];
    }
}

* i번째 계단까지 오는 경우의 수 (연속된 계단 3개 이상 XX)

  • i-3번째 계단을 거쳐서 i-1번째 계단
  • i-2번째 계단

* i-3 계층까지 재귀호출이 일어나므로 i < 3에 대한 초기값을 모두 세팅해야 함

 

9 1463 1로 만들기

정수 X에 사용할 수 있는 연산

  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    private static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        dp = new int[N+1];
        //dp[0] = dp[1] = 0;
        System.out.println(dp(N));
    }

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

*6으로 나누어 떨어지는 경우도 감안해야 한다.

 

10 10844 쉬운 계단 수 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static int mod = 1000000000;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        long[][] dp = new long[N+1][10];
        for(int i = 1; i < 10; i++) {
            dp[1][i] = 1;
        }

        for(int i = 2; i <= N; i++) {
            for(int j = 0; j < 10; j++) {
                if(j == 0) {
                    dp[i][j] = dp[i-1][1] % mod;
                } else if(j == 9) {
                    dp[i][j] = dp[i-1][8] % mod;
                } else {
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod;
                }
            }
        }

        long result = 0;
        for(int i = 0; i < 10; i++) {
            result += dp[N][i];
        }
        System.out.print(result % mod);
    }
}

 

11 2156 포도주 시식
  1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
  2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    private static int[] wine;
    private static Integer[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        wine = new int[N];
        dp = new Integer[N];
        for(int i = 0; i < N; i++) {
            wine[i] = Integer.parseInt(reader.readLine());
        }
        System.out.println(dp(N-1));
    }

    public static int dp(int n) {
        if(dp[n] == null) {
            if(n == 0) {
                dp[n] = wine[0];
            } else if(n == 1) {
                dp[n] = wine[0] + wine[1];
            } else if(n == 2) {
                dp[n] = Math.max(wine[0] + wine[1], Math.max(wine[0], wine[1]) + wine[2]);
            } else {
                dp[n] = Math.max(dp(n-1), Math.max(dp(n-3) + wine[n-1], dp(n-2)) + wine[n]);
            }
        }
        return dp[n];
    }
}

 

12 11053 가장 긴 증가하는 부분 수열

LIS(Longest Increasing Subsequence): 가장 긴 증가하는 부분 수열

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

public class Main {

    private static int[] arr;
    private static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        arr = new int[N];
        dp = new int[N];
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(tokenizer.nextToken());
        }
        int max = 0;
        for(int i = 0; i < N; i++) {
            if(max < lis(i)) {
                max = lis(i);
            }
        }
        System.out.println(max);
    }

    public static int lis(int n) {
        if(dp[n] == 0) {
            dp[n] = 1;
            for(int i = n - 1; i >= 0; i--) {
                if(arr[i] < arr[n]) {
                    dp[n] = Math.max(dp[n], lis(i) + 1);
                }
            }
        }
        return dp[n];
    }
}

*재귀 사용

*lis(i)+1의 1은 수열의 맨 뒤에 arr[n]이 추가된 것이다.

 

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

public class Main {

    private static int[] arr;
    private static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        arr = new int[N];
        dp = new int[N];
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(tokenizer.nextToken());
        }

        int max = 0;
        for(int i = 0; i < N; i++) {
            dp[i] = 1;
            for(int j = 0; j < i; j++) {
                if(arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            if(max < dp[i]) {
                max = dp[i];
            }
        }
        System.out.println(max);
    }
}

*반복문 사용

 

13 11054 가장 긴 바이토닉 부분 수열 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static int N;
    private static int[] arr;
    private static int[] dp1;
    private static int[] dp2;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(reader.readLine());
        arr = new int[N];
        dp1 = new int[N];
        dp2 = new int[N];
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(tokenizer.nextToken());
        }
        int max = 0;
        for(int i = 0; i < N; i++) {
            if(max < lis(i) + lds(i)) {
                max = lis(i) + lds(i);
            }
        }
        System.out.println(max - 1);
    }

    public static int lis(int n) {
        if(dp1[n] == 0) {
            dp1[n] = 1;
            for(int i = n - 1; i >= 0; i--) {
                if(arr[i] < arr[n]) {
                    dp1[n] = Math.max(dp1[n], lis(i) + 1);
                }
            }
        }
        return dp1[n];
    }

    public static int lds(int n) {
        if(dp2[n] == 0) {
            dp2[n] = 1;
            for(int i = n + 1; i < N; i++) {
                if(arr[i] < arr[n]) {
                    dp2[n] = Math.max(dp2[n], lds(i) + 1);
                }
            }
        }
        return dp2[n];
    }
}

 

*lis에서 lds로 변화하는 기준이 되는 수(Sk)가 중복되기 때문에 결과에서 1을 뺀다.

 

14 2565 전깃줄

 

 

15 9251 LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열): 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제

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

public class Main {

    private static String a;
    private static String b;
    private static Integer[][] dp;


    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        a = reader.readLine();
        b = reader.readLine();
        dp = new Integer[a.length()][b.length()];
        System.out.println(dp(a.length() - 1, b.length() - 1));
    }

    public static int dp(int x, int y) {
        if(x < 0 || y < 0) {
            return 0;
        }
        if(dp[x][y] == null) {
            dp[x][y] = 0;
            if(a.charAt(x) == b.charAt(y)) {
                dp[x][y] = dp(x-1, y-1) + 1;
            } else {
                dp[x][y] = Math.max(dp(x-1, y), dp(x, y-1));
            }
        }
        return dp[x][y];
    }
}

 

16 12865 평범한 배낭 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[] W;
    static int[] V;
    static int K;
    static Integer[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        W = new int[N+1];
        V = new int[N+1];
        dp = new Integer[N+1][K+1];
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(reader.readLine());
            W[i] = Integer.parseInt(st.nextToken());
            V[i] = Integer.parseInt(st.nextToken());
        }
        System.out.print(dp(N, K));
    }

    static int dp (int i, int w) {
        if(i < 0 || w < 0 || K < w) {
            return 0;
        }
        if(dp[i][w] == null) {
            if(i == 0 || w == 0) {
                dp[i][w] = 0;
            } else {
                if(w >= W[i]) {
                    dp[i][w] = Math.max(dp(i - 1, w), dp(i - 1, w - W[i]) + V[i]);
                } else {
                    dp[i][w] = dp(i - 1, w);
                }
            }
        }
        return dp[i][w];
    }
}

Knapsack 문제

-W: 물건의 무게

-V: 물건의 가치

-K: 배낭의 무게 한도

-dp[N][K]: N은 물건의 개수(0~N)

 

dp( i , w )

i: i번째 물건까지 고려해서 / w: 무게가 w일 때 최적값( dp[i][w] )을 구하는 메서드

i번째 물건의 무게가 w보다 작거나 같은 경우 배낭에 넣을 수 있다. (w <= K)

이때 최적값은 아래의 경우 중 가치가 높은 값이다.

  • i번째 물건을 넣지 않음 ( dp(i - 1, w) )
  • i번째 물건을 넣음 ( dp(i-1, w - W[i]) + V[i] ) (배낭의 무게가 w-W[i] 인 상태에서 i번째 물건을 넣어야 무게가 w가 됨)

i번째 물건의 무게가 w보다 큰 경우 물건을 넣는 선택지가 사라진다.