[백준] 11053번 : 가장 긴 증가하는 부분 수열 with python3, cpp

19 Aug 2018

Reading time ~1 minute

푸는 방법

aa에 있는 원소들을 전부 다 돈다.
dd는 해당 index까지의 숫자들 중 가장 긴 증가하는 부분 수열의 길이를 저장한다.
i는 처음부터 i 까지 앞에 있는 모든 숫자들과 비교를 한다.
만약 j보다 i가 큰 데, 부분수열의 길이가 만약에 j가 크면 dd[j]에 1을 더해서 i번째에 넣는다.
전에 있던 값과 대소비교를 하지 않아도 되는 이유는 어차피 작은 값들은 뒤에 큰 값에 경우의 수에 포함되어 있기 때문이다.
dd의 값 중 가장 값을 답으로 한다.

n = int(input())
aa = list(map(int, input().split()))
dd = [1]*(n+1)

for i in range(0,n):
    for j in range(0,i):
        if aa[j] < aa[i] and dd[j] >= dd[i]:
            dd[i] = dd[j] + 1

print(max(d))

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i=0; i<n; i++) {
      cin >> a[i];
  }
  vector<int> d(n);
  for (int i=0; i<n; i++) {
      d[i] = 1;
      for (int j=0; j<i; j++) {
          if (a[j] < a[i] && d[j]+1 > d[i]) {
              d[i] = d[j]+1;
          }
      }
  }  
  cout << *max_element(d.begin(),d.end()) << '\n';
  return 0;
}

d는 그 숫자를 기준으로 가장 긴 수열을 값에 넣는다.

algorithm 백준