[DP] LIS, LCS, MCM

-LIS ( 가장 긴 증가하는 부분 수열 ) 이다.

 

n^2 방법은 알고있으니 nlog2n으로 하자.

BASE는

www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

 

 

import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main {
 
    static int n;
    static int arr[]; // 입력용
    static int lis[]; // 이것의 length == 가장 긴 증가하는 수열이다. BUT 수열의 배열이 trace값은 아니다.
    static int prev[]; // 수열 trace용
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        lis = new int[n];
        prev = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i = 0 ; i < n ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            lis[i] = 1;
            prev[i] = 0;
        }
        
        int max = 1;
        lis[0] = arr[0];
        
        for(int i = 1 ; i < n ; i++) {
            if(lis[max-1] < arr[i]) {
                lis[max] = arr[i];
                prev[i] = max;
                max++;
            }
            else {  // arr[i]를 lis의 특정위치에 넣기 위해 lowerBound 해준다.
            
                int low = 0;
                int high = max;
                int mid;
                
                while(low < high) {
                    mid = (low+high)/2;
                    if(lis[mid] < arr[i])
                        low = mid+1;
                    else
                        high = mid;
                }
                
                lis[high] = arr[i];
                prev[i] = high;
                
            }
        }
        
        System.out.println(max);
        // 수열 따라가기
        Stack<Integer> s = new Stack<Integer>();
        
        for(int i = n-1 ; i>= 0 ; i--) {
            if(prev[i] == max-1) {
                s.add(arr[i]);
                max--;
            }
        }
        
        while(!s.isEmpty())
            bw.write(s.pop() + " ");
        bw.close();
        
        
    }
}

 

 

-LCS  최장 공통 부분 문자열 이다. 이걸 대충 보면 된다.

trace는 d[i][j] 에서 위에도, 왼쪽에도 다른 수일때 문자를 뽑으면 된다.

Base문제는

www.acmicpc.net/problem/9252

9252번: LCS 2

import java.util.*;
import java.io.*;
import java.math.*;
 
public class D210412_boj9252_LCS2 {
 
    static int n;
 
    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String str = br.readLine();
        String str2 = br.readLine();
        int len1 = str.length();
        int len2 = str2.length();
        char[] c1 = new char[len1+1];
        char[] c2 = new char[len2+1];
        int[][] d = new int[c1.length][c2.length];
        
        for(int i = 1 ; i <= len1; i++)
            c1[i] = str.charAt(i-1);
        for(int i = 1 ; i<= len2; i++)
            c2[i] = str2.charAt(i-1);
        
        
        for (int i = 1; i <= len1; i++)
        {
            for (int j = 1; j <= len2; j++)
            {
                if (c1[i] == c2[j])
                    d[i][j] = d[i - 1][j - 1] + 1;
                else
                    d[i][j] = Math.max(d[i - 1][j], d[i][j - 1]);
            }
        }
        
        System.out.println(d[len1][len2]);
        char[] stack = new char[1005];
        int stack_size = 0;
        StringBuilder sb = new StringBuilder();
        
        while(true) {
            if (d[len1][len2] == 0)
                break;
 
            if (d[len1][len2] == d[len1 - 1][len2])
                len1--;
            else if (d[len1][len2] == d[len1][len2 - 1])
                len2--;
            else
            {
                sb.append(c1[len1]);
                len1--;
                len2--;
            }
        }
        
        System.out.println(sb.reverse());
    }
}
 

- MCM

행렬 곱셈등에서 대각 DP를 쓰기 위해 사용하는 DP 방식이다. 

BASE문제는

www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

파일 합치기 문제도 이것과 비슷하다.

 

import java.util.*;
import java.io.*;
import java.math.*;
 
public class D210413_boj11049_행렬곱셈순서 {
 
    static final int INF = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        int[] arr = new int[n+1];
        int[][] d = new int[n+1][n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr[0] = Integer.parseInt(st.nextToken());
        arr[1] = Integer.parseInt(st.nextToken());
        
        
        /*
         * 5 3 -> 3 2 -> 2 6 의 순서를 가진다 하면
         * arr 는 5 3 2 6 이렇게 저장을 한다.
         * 
         */
        for(int i = 1 ; i < n ; i++) {
            st = new StringTokenizer(br.readLine());
            st.nextToken();
            arr[i+1] = Integer.parseInt(st.nextToken());
        }
        /*
         * 대각선 방식의 DP 탐색을 하자.
         * d[1][2] -> d[2][3] -> d[3][4] -> d[1][3] -> d[2][4] -> d[1][4] 이렇게.
         * cha를 1-> 2-> ..... -> n-1 하면 된다.
         */
        for(int cha = 1 ; cha < n ; cha++) {
            for(int i = 1 ; i <= n-cha ; i++) {
                int j = i+cha;
                d[i][j] = INF;
                for(int k = i ; k < j ; k++) {
                    int tmp = d[i][k] + d[k+1][j] + arr[i-1]*arr[k]*arr[j];
                    if(d[i][j] > tmp)
                        d[i][j] = tmp;
                }
            }
        }
        
        System.out.println(d[1][n]);
        
    }
}