[BOJ 11055] 가장 큰 증가하는 부분 수열

다이나믹 프로그래밍에서 가장 중요한것은 테이블을 어떻게 정의하는것이다.

항상 문제를 푼다는 마음이 급해서 테이블 정의를 소홀히해서 오히려 문제를 못풀고 헤매는 경우가 많았다.

따라서 DP 문제는 반드시 테이블을 정의하는것이 시작이라는것을 깨달아야 한다.

 

테이블에 따라서 문제가 간편해 질수도 복잡해 질수도있다.

(일단 테이블이 내가 말하는대로 생각한대로 무조건 동작한다고 가정하자.)

테이블만 잘 설계하면 나머지 조건식들은 적절히 구성해서 답을 도출할수 있다.

수학처럼 점화식으로 떨어지기도 하거나 전에 구했던 식에서 한단계씩 확장하는 모습일수도 있다.

 

이문제에서는 증가하는 수열의 합인데 DP로 풀지 않는다면 증가하는 이라는 조건을 그때그때 조건식으로 추려내기가 쉽지가 않다.

그렇다면 DP를 이용해서 전단계에서 한단계씩 확장하는 방법을 사용해보자.

테이블 D[i]는 수열 a[i]까지 증가하는 수열의 합이라고 할때 나중에 a[i+k]가 만약 a[i] 보다 크다면 수열 처음부터 증가하는 수열을 다 더하는것이 아니라 D[i]까지 이미 구해 놓았기 때문에 거기서부터 한단계만 확장하기만 하면 된다는 아이디어를 캐치하자.

그리고 거기다만 a[i+k]를 더해주고 기존의 d[i]에서 큰값을 비교해서 갱신해주기만 하면 문제는 끝난다.

 

코드와 주석은 아래와 같다.

 

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

int d[1005]; // d[n] : a[n]이 수열의 마지막일때 증가하는 수열의 합
int a[1005]; // 수열 원본

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  int n;
  cin >> n;

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

  for(int i=1; i<n+1; i++){
    for(int j=1; j<i; j++){
      if(a[i] > a[j]) d[i] = max(d[i], d[j] + a[i]); // 유지 or 갱신
    }
  }

  cout << *max_element(d+1, d+n+1) << '\n';


  
  
}