[11055번] 가장 큰 증가 부분 수열

문제 출처 :

https://www.acmicpc.net/problem/11055

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 동적 프로그래밍을 위한 문제 이해

아래 그림에 대해서 설명을 하자면,

arr은 값을 받아오는 배열이고, DP는 증가하는 부분수열의 합을 저장하는 곳이다.

max는 그 부분수열이 증가하는지 확인해주고, 증가한다면 최댓값을 가지고 있는 저장소이다.

arr[0]과 arr[1]을 비교해 본다면,

arr[1]이 10이므로 더 크니깐, max에는 DP[0]를 넣어준다. 

이후 DP[1]의 값을 채워준다.

마찬가지로 계속 반복을 해보면 10 11 10 11부분에서는

11이 10보다 커서 DP가 22가 되었지만 그다음에서는 10은 1보다 커서 max를 1을 가지고 있는데

10과는 같아서 넘어가고 11보다는 작아서 넘어간다.

따라서 최종 max는 1임을 알 수 있고, arr[3]의 DP[3]은 11이라는 것을 도출 할 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

#include <iostream> #include <algorithm> using namespace std;   int dp[1001]; int arr[1001];   bool comp(const int &a, const int &b) {     return a > b; }   int main() {     int n;     int max = 0;     int tmp = 0;          cin >> n;       for (int i = 0; i < n; i++)         cin >> arr[i];           dp[0] = arr[0];          for (int i = 1; i < n; i++)     {         max = 0;                  for(int j = 0 ; j < i ; j ++)         {             if (arr[i] > arr[j])             {                 tmp = dp[j];                   if(tmp >= max)                     max = dp[j];             }                      }         dp[i] = max + arr[i];     }          sort(dp, dp + n, comp);       cout << dp[0]; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus