백준 11055 가장 큰 증가 부분 수열(dynamic programming)

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

#include <iostream>   using namespace std;   const int MAX=1000; int N; int arr[MAX]; int cache[MAX]; int sum;   void maxSum(){     for(int i=0;i<N;i++){         cache[i]=arr[i];         for(int j=0;j<=i;j++){             if(arr[i]>arr[j]&&cache[i]<cache[j]+arr[i])             cache[i]=cache[j]+arr[i];             sum=max(sum,cache[i]);         }     }     cout<<sum; }   int main(){     ios::sync_with_stdio(false);     cin.tie(NULL);     cin>>N;     for(int i=0;i<N;i++)     cin>>arr[i];     maxSum(); } Colored by Color Scripter

cs

 

for(int i=0;i<N;i++){

        cache[i]=arr[i];

        for(int j=0;j<=i;j++){

            if(arr[i]>arr[j]&&cache[i]<cache[j]+arr[i])

            cache[i]=cache[j]+arr[i];

            sum=max(sum,cache[i]);

        }

    }

 

이 부분을 중점적으로 확인해야 한다.

i: 배열의 어느 부분까지의 합을 확인할 것인지.

j: 처음부터 i까지의 가장 큰 부분 수열을 확인.

 

i를 늘려나가면서 가장 큰 부분 수열을 찾는 문제이다.

 

if(arr[i]>arr[j]&&cache[i]<cache[j]+arr[i])

if문의 조건을 둘로 나눌 수 있다.

 

1)arr[i]>arr[j] 증가수열이어야하기 때문에 이 조건이 성립해야한다.

 

2)cache[i]<cache[j]+arr[i]

 

cache[i]는 i까지의 가장 큰 부분 수열, cache[j]는 j까지의 가장 큰 부분 수열을 의미한다.

만약 cache[j]+arr[i]의 값이 cache[i]보다 크다면, 이 값이 가장 큰 부분 수열이기 때문에 갱신한다.