[문제풀이] 백준 11053 - 가장 긴 증가하는 부분 수열

📢 문제

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

📢 알고리즘

DP(동적 계획법)

📢 풀이

#include <iostream>

using namespace std;

int arr[1001] = {0}; //주어진 수열
int DP[1001] = {0}; //arr[i]를 포함하는, i까지의 증가수열 최대 길이

int main()
{
  int N;       //수열의 크기
  int ans = 0; //증가수열 최대 길이
  cin >> N;

  for (int i = 1; i <= N; i++)
  {
    cin >> arr[i];
  }

  // arr[0] = 0
  for (int i = 1; i <= N; i++)
  {
    int max = 0; //현재 i-1까지 증가 부분수열 최대 길이
    for (int j = 0; j < i; j++)
    {
      if (arr[i] > arr[j] && DP[j] >= max)
      {
        max = DP[j];
      }
    }
    DP[i] = max + 1;
    if (DP[i] > ans)
    {
      ans = DP[i];
    }
  }

  cout << ans;
}

• DP[i] : arr[i]를 포함하는, i까지의 증가수열 최대 길이

• for (int i = 1; i <= N; i++)

  • arr 배열에서 i번째까지 고려

• for (int j = 0; j < i; j++)

  • arr 배열에서 0(arr[0]=0, 의미없는 수, i=1을 위해 범위에 포함)~i-1번째까지 고려

• max : i-1까지 증가수열 최대 길이

• if(arr[i] > arr[j] && DP[j] >= max)

  • i번째 이전의 수는 i번째 수보다 작아야함(증가수열이니까)

  • j를 포함하는, j까지의 증가수열 최대길이 >= j-1까지의 증가수열 최대길이(j-1을 포함하지 않을 수도 있음) 일때만 max를 갱신

    • DP[j] < max인 수를 증가수열에 포함하면 오히려 증가수열 길이가 줄어듦
    • 최대길이가 더 작은 수열로 대체되니까...

• DP[i] = max + 1;

  • DP[i]는 i번째 수도 포함해야 하니까 +1

그나저나 DP문제 진짜 졸라게 어렵다... 내가 멍청인건가? 실버2인데도.. 이런 생각을 대체 어떻게 하지????

📖 참고자료
https://wootool.tistory.com/96 - 코드, gif