[백준/C++] 알고리즘 11055번 - 가장 큰 증가하는 부분 수열

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 11055번 - 가장 큰 증가하는 부분 수열을 풀어보도록 하겠습니다.

 

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

 

[문제 접근]

제한시간은 1초이고 n은 1000이하입니다. 완전탐색은 합까지 포함해서 대략 O(N^3)으로 10억의 연산이 필요하기 때문에 불가능합니다.

연속하는 것이 아니기 때문에 투 포인터를 사용하는 것도 어렵습니다. 다시 문제를 살펴보면 수열의 크기가 n일 때와 n-1일 때와 비교해보면 1. 같다.

2. n이 a[n-1]만큼 더 크다.

임을 알 수 있습니다. 즉 n 상황과 n-1상황이 서로 관계가 있음을 파악할 수 있고, 이를 통해 다이나믹 프로그래밍 풀이를 생각해볼 수 있습니다. 그럼 배열을 정의하고 점화식을 세우면 됩니다.

 

이 때 d[i]를 어떻게 정의를 할까가 되게 막막합니다.

 

n= 5 일 때의 상황을 살펴보면

1 100 2 50 60

d[i]를 크기가 i인 수열에서 가장 큰 부분 수열의 합이라고 일반적으로 정의를 내리면 d[4] =  1+2+50+60입니다.

 

n = 4 일때 상황을 살펴보면

d[3] = 1+ 100 입니다. 

 

즉 d[4]와 d[3]이 얻어지는 패턴양상이 달라 점화식을 찾아내기가 어렵습니다.

 

d[i]의 재정의가 필요합니다.

i= 5일때 d[4]에 a[4]가 들어간다는 점과

i = 2일때 d[1]에 a[1]가 들어간다는 점을 생각했을 때,

d[i] = a[i]를 포함하는 가장 큰 증가하는 부분 수열의 합 으로 정의를 내려봅시다.

그럼 가장 큰 증가하는 부분수열의 합은 이전에 저장한 가장 큰 증가하는 부분 수열 중에 최댓값이라고 생각할 수 있습니다.

 

이제 점화식을 찾아야하는 데, 이것도 어렵습니다.

i = n일 때, i = 0부터 i = n-1까지 증가하는 수를 찾고 계속 더해가야 합니다. 

즉  d[0]부터 d[n-1]을 확인하면서 (d[j]를 확인하면서)  a[i]와 더했을 때 최댓값을 찾아야 합니다.(단, a[j] < a[i]를 만족해야함)

즉 이중 for문을 돌면서 d[i] = max(d[i], d[j]+a[i]) 점화식을 세울 수 있습니다. ( 여기서 j < i ) 

 

[풀이 전략]

1. d[i]를 a[i]로 초기화합니다.

2. 이중 for문을 돌면서 a[j] < a[i] 이면  d[i] = max(d[i], d[j]+a[i]) 점화식을 이용하여 d[i]를 계산합니다.

3.d[0]부터 d[n-1]까지의 최댓값을 출력합니다.

 

[코드]

#include <iostream>
#include <algorithm>
using namespace std;



int n ; 
int a[1001];
int d[1001];

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

    cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    d[i] = a[i];
  }
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < i; ++j)
      if (a[j] < a[i]) d[i] = max(d[i], d[j] + a[i]);
  
  cout << *max_element(d, d + n);
}

 

[배울 점]

- 예시 속에서 패턴을 찾을 때, n과 n-1비교해서 잘 안되면 그 이전 상황들도 비교해가며 패턴 양상이 같은 것을 토대로 점화식 찾아보기.