[C++] BOJ 11053번: 가장 긴 증가하는 부분 수열, 11055번: 가장 큰 증가 부분 수열,. 11722번: 가장 긴 감소하는 부분 수열

문제 링크

문제 풀이

해당 문제를 DP(Dynamic Programming) 알고리즘을 이용하여 해결할 수 있다.

11053번, 11722번 : dp[i] = dp[0]부터 dp[i-1]까지의 값 중 최대값 + 1

11055번 : dp[i] = dp[0]부터 dp[i-1]까지의 값 중 최대값 + arr[i]

코드 (11053번)

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[1004];

int dp[1004];
int maxdp;
int result;

void calcDp()
{
    for (int i = 0; i < N; i++)
    {
        int maxdp = 0;
        for (int j = 0; j < i; j++)
        {
            if (arr[i] > arr[j])
            {
                maxdp = max(maxdp, dp[j]);
            }
        }
        dp[i] = maxdp + 1;
        result = max(result, dp[i]);
    }
}

int main(void)
{

    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }

    calcDp();

    cout << result << '\n';

    return 0;
}

코드 (11055번)

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[1004];

int dp[1004];
int maxdp;
int result;

void calcDp()
{
    for (int i = 0; i < N; i++)
    {
        int maxdp = 0;
        for (int j = 0; j < i; j++)
        {
            if (arr[i] > arr[j])
            {
                maxdp = max(maxdp, dp[j]);
            }
        }
        dp[i] = maxdp + arr[i];
        result = max(result, dp[i]);
    }
}

int main(void)
{

    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }

    calcDp();

    cout << result << '\n';

    return 0;
}

코드 (11722번)

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[1004];
int dp[1004];
int result;

void calcDp()
{
    for (int i = 0; i < N; i++)
    {
        int maxdp = 0;
        for (int j = 0; j < i; j++)
        {
            if (arr[i] < arr[j])
                maxdp = max(maxdp, dp[j]);
        }
        dp[i] = maxdp + 1;
        result = max(result, dp[i]);
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 0; i < N; i++)
        cin >> arr[i];

    calcDp();

    cout << result << '\n';

    return 0;
}