[백준 11055] 가장 큰 증가 부분수열

문제출처: https://www.acmicpc.net/problem/11055

풀이

약 3주만에 알고리즘 문제를 다시 풀어보려는데 감이 많이 떨어져서 쉬운 문제를 찾다가 풀어본 문제입니다.

대충 문제를 읽고 dp문제같아서 dp로 풀었는데 맞았습니다. 

arr[i]>arr[j]일 때 ( 앞의값보다 뒤의값이 클 때) dp[i]값을 갱신하는 식만 작성할줄 알면 될 것 같습니다.

코드

#include<iostream>
#include<algorithm>
int arr[1001], dp[1001];
using namespace std;
int main()
{
    int n, sum = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        //arr[i]값을 dp에 복사한다.
        dp[i] = arr[i];
        //하나씩 비교해보며 가장 큰 증가부분수열구함
        for (int j = 0; j <= i; j++)
        {
            // [1, 100, 2] 일 때
            //증가수열이므로 무조건 뒷값이 앞값보다커야함
            if (arr[i] > arr[j])
            {
                //정답인dp[i]값을 갱신시켜나감
                if (dp[i] < dp[j] + arr[i])dp[i] = dp[j] + arr[i];
            }
        }
        //정답을 갱신시킴
        sum = max(sum, dp[i]);
    }
    cout << sum << endl;
}

결과