[백준/C++] 11055번_가장 큰 증가 부분 수열

문제는 다음과 같습니다.

일단 백준 너무 오랜만입니다,,
저번주까지 해커톤 준비하느라 막판에 에러가 터져서 에러해결하느라
백준 일주일만에 풀게 되었습니다.
다시 정신차리고 하루에 한문제 이상씩 꼭 풀겠습니다!

계속 이어서 DP입니다.

앞 문제 중에서도 이와 비슷한 문제가 많았구요.
핵심은 다음과 같습니다.

• i번째 배열을 포함한 수까지의 최대 증가 부분 수열의 합을 s라는 벡터에 계산을 해주었습니다.
• 그리고 i번째 배열의 값은 배열 a[i]에 넣어, for문을 도는 와중에도 이전 값을 참조할 수 있게 하였습니다.

그리고 입력을 받으면서 바로 그 수에 대한 a[i]와 s[i]의 값을 계산해주었습니다.

s[i]의 값은 변수 j가 0부터 i-1까지의 다시 돌면서,

• a[j]<a[i] : 증가 수열의 조건
• s[j]>t_max : 이전까지의 증가 수열의 합 중 최대값 찾기

이 두 조건을 만족하는 s[j]를 찾아, t_max를 갱신하도록 하였습니다.

제 전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

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

    int a[1000]={0, };
    vector<int> s;
    int n, tmp, j, t_max;
    cin>>n;
    cin>>tmp;
    a[0]=tmp; s.push_back(tmp);

    for(int i=1; i<n; i++){
      cin>>tmp; a[i]=tmp;

      j=i-1;
      t_max=0;
      while(j>=0){
        if(a[j]<tmp && s[j]>t_max) t_max=s[j];
        j--;
      }
      s.push_back(t_max + tmp);
    }
    
    cout<<*max_element(s.begin(), s.end())<<endl;
    return 0;
}