패스트캠퍼스 챌린지 34일차

동적 프로그래밍 3 😢

 

파일 합치기 (BOJ 11066)

1. 각자의 크기가 존재하는 파일들이 순서대로 존재한다.

2. 연속한 두 파일을 하나로 합치면, 합친 크기 만큼의 비용이 필요하다.

3. 전체 K개의 파일들을 하나로 합치는 방법들 중에서 총 비용의 최솟값을 계산하라.

 

점화식 구해내기 (i = 짜르기 시작한 부분, K는 i 이후 자른 시작 부분, j는 마지막 부분)

 - Dy[i][j] = min { Dy[i][k] + Dy[k+1][j] + (i~j 파일 총량) (i <= K < j) 

   sum[i][j] = i번 ~ j번 파일의 총 크기 = Sum[i][j-1] + A[j] 

 

짧은 구간부터 먼저 배열을 채워 나가야 한다.

	static int K, Q;
	static int[] num;
	static int[][] Dy, sum;

    static void input(){
        K = scan.nextInt();
        num = new int[K + 1];
        sum = new int[K + 1][K + 1];
        for (int i = 1; i <= K; i++){
            num[i] = scan.nextInt();
        }
    }

    static void preprocess(){
        for (int i = 1; i <= K; i++){
            for (int j = i; j <= K; j++){
                sum[i][j] = sum[i][j - 1] + num[j];
            }
        }
    }

    static void pro() {
        preprocess();
        Dy = new int[K + 1][K + 1];

        for (int len = 2; len <= K; len ++){
            for (int i = 1; i <= K - len + 1; i++){
                int j = i + len - 1;
                Dy[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++){
                    Dy[i][j] = Math.min(Dy[i][j], Dy[i][k] + Dy[k + 1][j] + sum[i][j]);
                }
            }
        }

        System.out.println(Dy[1][K]);
    }

 

트리와 쿼리 (BOJ 15681, 중요)

 - Rooted Tree에서 정점이 주어질 떄마다, 정점에 대한 subtred에 속한 정점의 개수를 계산하라

   

문제 정의

 Dy[i] : i를 root로 하는 subtree의 정점 개수

 

초기값

 - "단말 노드"가 제일 작은 문제이다 => 정점이 한 개 뿐이라서!

 

Dy[부모 노드] = SUM Dy[자식노드들] + 1 (본인 노드)

 

구현

 	static int N, R, Q;
 	static ArrayList<Integer>[] con;
	static int[] Dy;

    static void input(){
        N = scan.nextInt();
        R = scan.nextInt();
        Q = scan.nextInt();
        con = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++){
            con[i] = new ArrayList<>();
        }
        for (int i = 1; i < N; i++){
            int x = scan.nextInt(), y = scan.nextInt();
            con[x].add(y);
            con[y].add(x);
        }
    }

    // Dy[x] 를 계산하는 함수
    static void dfs(int x, int prev){
        Dy[x] = 1; // 나를 Root로 하는 Subtree는 최초 1을 가져야 한다
        for (int y: con[x]){ 
            if (y == prev) continue; // 부모 노드는 제외
            dfs(y, x); // 자식노드 일 경우 다시 dfs함수 실행
            Dy[x] += Dy[y]; // 자식 노드들을 계속 더한다
        }
    }

    static void pro() {
        Dy = new int[N + 1];

        dfs(R, -1);

        for (int i = 1; i <= Q; i++){
            int q = scan.nextInt();
            sb.append(Dy[q]).append('\n');
        }
        System.out.println(sb);
    }

 

 

우수 마을 (BOJ 1949)

 - 인접하지 않은 마을들을 골라서 주민 수의 총합을 최대화

 

1) 문제 정의

 Dy[i][0] : i를 root로 하는 subtree에서 root를 선택하지 않고서 가능한 최대 주민 수

 Dy[i][1] : i를 root로 하는 subtree에서 root를 선택하고서 가능한 최대 주민 수

 

점화식

 Dy[Root.R][1] = num[R] + Dy[child[0]의 합 // R이란 정점을 고른 순간 R의 자식 노드들은 고를 수 없다.

 

 	static int N;
	static int[] num;
	static ArrayList<Integer>[] con;
	static int[][] Dy;

    static void input(){
        N = scan.nextInt();
        num = new int[N + 1];
        con = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++){
            num[i] = scan.nextInt();
            con[i] = new ArrayList<>();
        }
        for (int i = 1; i < N; i++){
            int x = scan.nextInt(), y = scan.nextInt();
            con[x].add(y);
            con[y].add(x);
        }
    }

    static void dfs(int x, int prev){
        Dy[x][1] = num[x];
        for (int y: con[x]){
            if (y == prev) continue;
            dfs(y, x);
            Dy[x][0] += Math.max(Dy[y][0], Dy[y][1]);
            Dy[x][1] += Dy[y][0];
        }
    }

    static void pro() {
        Dy = new int[N + 1][2];

        dfs(1, -1);

        System.out.println(Math.max(Dy[1][0], Dy[1][1]));
    }

    public static void main(String[] args) {
        input();
        pro();
    }

 

 

34일차 인증

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]