(13) [C++, Java] 백준 No.11722 : 가장 긴 감소하는 부분 수열

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-13-DP-문제-풀이3-3-백준-No11722-가장-긴-감소하는-부분-수열

 

# C++(reverse해서 가장 긴 증가하는 부분 수열의 길이를 구하는 방법을 사용)

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    vector<int> d(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    // 역순으로 변경
    reverse(a.begin(), a.end());

    // 가장 긴 증가하는 부분 수열의 길이를 구하는 방법 이용
    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;
        }
    }

    cout << *max_element(d.begin(), d.end()) << "\n";
}

# C++(왼쪽->오른쪽 방향으로 가장 긴 증가하는 부분 수열의 길이를 구하는 방법을 사용)

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    vector<int> d(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];

    // 역순으로 가장 긴 증가하는 부분 수열의 길이를 구하는 방법 이용
    for (int i = n-1; i >= 0; i--)
    {
        d[i] = 1;

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

    cout << *max_element(d.begin(), d.end()) << "\n";
}

# Java

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);
    }
}