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

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

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

 

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

11053번: 가장 긴 증가하는 부분 수열

 

[문제 접근]

바로 이전 글에서 풀었던 가장 큰 증가하는 부분 수열과 문제 접근 방식이 동일해서 생략합니다.

아래 글을 참고해주세요.

https://techgineer22.tistory.com/17

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

 

 

[풀이 전략]

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

2. 이중 for문을 돌면서 a[j] < a[i] 이면  d[i] = max(d[i], d[j]+ 1) 점화식을 이용하여 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];
    fill(d, d+ n , 1);
   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] + 1);
  
  cout << *max_element(d, d + n);
}

 

[배울 점]

- d[i]의 정의는 이전 상황들을 비교해서 정의 하기.