21.07.22 - [BOJ] 11722. 가장 긴 감소하는 부분 수열

[suhyunsim]

문제

• 11722

핵심 아이디어

• 방법1: 가장 긴 증가하는 수열 그대로 이용
  • D[i]: A[i]에서 끝나는 가장 긴 감소하는 부분 수열의 길이
  • 부등호만 반대로 풀이
• 방법2: 새로운 점화식 이용
  • D[i]: A[i]에서 시작하는 가장 긴 감소하는 부분 수열의 길이
  • i < j, A[i] > A[j]
  • D[i] = max(D[j]) + 1
  • N -> 1

어려운 점, 실수

풀이

방법1: 등호만 다르게

package main.java.com.poogle.BOJ.Q11722;

import java.util.Scanner;

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

방법2: 새롭게

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+1];
        int[] d = new int[n+1];
        for (int i=1; i<=n; i++) {
            a[i] = sc.nextInt();
        }
        for (int i=n; i>=1; i--) {
            d[i] = 1;
            for (int j=i+1; j<=n; j++) {
                if (a[i] > a[j] && d[i] < d[j]+1) {
                    d[i] = d[j]+1;
                }
            }
        }
        int ans = d[1];
        for (int i=2; i<=n; i++) {
            if (ans < d[i]) {
                ans = d[i];
            }
        }
        System.out.println(ans);
    }
}