백준 1932번 정수 삼각형

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[][] = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                a[i][j] = sc.nextInt();
            }
        }

        int d[][] = new int[n][n];
        d[0][0] = a[0][0];
        for(int i = 1; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                d[i][j] = d[i - 1][j] + a[i][j];
                if(j - 1 >= 0 && d[i][j] < d[i - 1][j - 1] + a[i][j]) {
                    d[i][j] = d[i - 1][j - 1] + a[i][j];
                }
            }
        }

        int answer = d[n - 1][0];
        for(int i = 0; i < n; i++) {
            answer = Math.max(answer, d[n - 1][i]);
        }
        System.out.println(answer);
    }
}

어떤 수가 선택되기 전에 선택된 수는 대각선 왼쪽 위, 오른쪽 위에 있는 것이다.

D[i][j] = i행 j열이 선택되었을 때, 최대합
(i, j)가 선택되기 전에 선택된 수는 (i-1,j),(i-1,j-1)중 하나다.

=> D[i][j] = Max(D[i-1][j], D[i-1][j-1]) + A[i][j]

결과

백준 11055번 가장 큰 증가하는 부분 수열

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        int d[] = new int[n];
        for(int i = 0; i < n; i++) {
            d[i] = a[i];
            for(int j = 0; j < i; j++) {
                if(a[j] < a[i] && d[i] < d[j] + a[i]) {
                    d[i] = d[j] + a[i];
                }
            }
        }
        
        int answer = d[0];
        for(int i = 0; i < n; i++) {
            answer = Math.max(answer, d[i]);
        }
        System.out.println(answer);
    }
}

LIS 문제에서 D[i] = D[j] + 1이 아니라 합을 구하는 것이므로 D[i] = D[j] + A[i]로 바꾸기만 하면 된다.

결과

백준 11722번 가장 긴 감소하는 부분 수열

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        int d[] = new int[n];
        for(int i = 0; i < n; i++) {
            d[i] = 1;
            for(int j = 0; j < i; j++) {
                if(a[j] > a[i]) {
                    d[i] = Math.max(d[i], d[j] + 1);
                }
            }
        }
        
        int answer = d[0];
        for(int i = 0; i < n; i++) {
            answer = Math.max(answer, d[i]);
        }
        System.out.println(answer);
    }
}

LIS 문제에서 a[j] a[i]를 비교하는 부등호 하나만 a[j] > a[i]로 변경해주면 된다.

D[i] = A[i]에서 끝나는 가장 긴 감소하는 부분 수열의 길이
D[i] = max(D[j]) + 1 (j < i && A[j] > A[i])

결과

백준 11054번 가장 긴 바이토닉 부분 수열

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        int d[] = new int[n];
        for(int i = 0; i < n; i++) {
            d[i] = 1;
            for(int j = 0; j < i; j++) {
                if(a[j] < a[i]) {
                    d[i] = Math.max(d[i] , d[j] + 1);
                }
            }
        }
        
        int d2[] = new int[n];
        for(int i = n - 1; i >= 0; i--) {
            d2[i] = 1;
            for(int j = i + 1; j < n; j++) {
                if(a[i] > a[j]) {
                    d2[i] = Math.max(d2[i], d2[j] + 1);
                }
            }
        }
        
        int answer = d[0] + d2[0] - 1;
        for(int i = 0; i < n; i++) {
            answer = Math.max(answer, d[i] + d2[i] - 1);
        }
        System.out.println(answer);
    }
}

가장 긴 증가하는 부분 수열(D)과 가장 긴 감소하는 부분 수열(D2)를 구한 다음
D[i] = i에서 끝나는 가장 긴 증가하는 부분 수열
D2[i] = i에서 시작하는 가장 긴 감소하는 부분 수열
D[i] + D2[i] -1이 가장 큰 값을 찾으면 된다.

결과