[C] 11053: 가장 긴 증가하는 부분 수열

11503: 가장 긴 증가하는 부분 수열

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

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

 

DP 문제 풀이 정리!

Dynamic Programming 문제를 풀기 위한 생각을 잠시 정리해보면...

 

첫째, 배열을 이용하여 배열에 저장하며 문제를 풀어야하고

둘째, 점화식들을 이용해 작은 subproblems를 이용해 반복을 통하여 문제를 풀어야한다.

셋째, 만약 수학적으로 하나의 식이 만들어지지 않는다면 조건문을 이용하여 여러가지 점화식으로 표현하고

넷째, 각 배열의 순간까지 최적의 경우의 수를 구해, 이 subproblems를 가지고 결과를 도출해내는것이다.

 

점화식을 사용한다는 것은 동일한 작은 문제들이 반복(중복하기 때문에 미리 subproblem을 구하여 재활용하는 것이 효율적이며 이것이 Divide & Conquer와 가장 다른 점이다)하여 나타난다는 것을 의미하며 subproblem의 결과를 배열에 저장하여 재계산을 하지 않을 수 있어야한다. 이때 주의해야할 건 subproblem에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어야하는 것이며 이는 위에 '넷째'문제의 가정이 되기도 한다.

 

이를 다시 정리하면 DP 문제를 풀기 위해서 DP로 풀  수 있는 문제인지 확인하고 (주로 최대,최소 계산, 데이터 세기, 확률 계산) 문제의 변수들을 이용해 관계식을 만들어 배열에 저장(Memoization)하고 Bottom-Up이나 Top-down 방식을 이용해 풀어야한다.

 

이때 Bottom-Up 방식은 아래에서부터 계산을 수행한 것을 누적시켜 문제를 푸는 것인데 주로 반복문을 이용하여 결과값을 기억하여 재활용하는 방식이고 Top-Down은 위에서부터 호출을 시작하여 맨 마지막 상태까지 간 후 다시 재귀를 통해 재활용하는 방식이다. 주로 재귀를 이용하여 구현하며 단순히 메모리에 저장된 값을 활용하면 된다.

 

풀이!

 

이 순서를 따라 이 문제도 풀어게 되면 dp배열에 각 순간마다 최적의 경우의 수를 구하면 된다.

 특히 여기서는 시간복잡도가 O(n^2)인 알고리즘을 사용하고 있다. 여기서는 n번째 수가 있을 때 (1.)arr 배열의 수 중 arr[n]보다 작은 수 중에서 (2.)dp배열의 n-1번째까지 수 중에서 가장 큰 수에 +1을 하면된다.

 (1.) arr 배열의 수 중 arr[n]보다 작아야만 "증가하는 수열"이 될 수 있기 때문에 해당 문제의 조건을 만족할 수 있게 된다. 또한 (2.) arr[n]보다 작은 수 index 중에서 dp배열의 n-1까지 수중에 가장 큰  수를 찾아야지만 "가장 긴" 부분 수열이 될 수 있다. 찾은 dp배열의 값에 +1를 하면 쉽게 답을 구할 수 있다.

 

#include <stdio.h>

int main(void)
{
  int n;
  scanf("%d",&n);
  int arr[n];
  for(int i=0;i<n;i++)
    {
      scanf("%d",&arr[i]);
    }
  int dp[n]; //현재까지 배열 중에 가장 긴 증가하는 부분 수열의 길이를 저장
  for(int i=0;i<n;i++)
    dp[i]=0;
  dp[0]=1;
   for(int j=1;j<n;j++)
    {
      int max=0; //k는 j보다 작은 수
        for(int k=j-1;k>=0;k--) //arr[j]보다 작은 수중에 최댓값 찾기
          {
            if(arr[k]<arr[j]&&arr[k]>max) //그 최댓값이 dp배열에서 최대인지 확인하기
            {
              max=arr[k];
              if(dp[k]>=dp[j]) //=을 붙어야함, +1을하면 dp[k]가 더 커지기 떄문
                dp[j]=dp[k]+1; //dp의 값 갱신
            }            
          }   
      if(dp[j]==0)//예를 들어 arr[]={100,1,2}일때 현재 dp는 0으로 초기화되어있으므로 최댓값이 없더라도 dp[1]값을 1로 만들어줘야한다
        dp[j]=1;

     // printf("%d: %d\n",j,dp[j]);
        
    }
    int max=0;
  for(int i=0;i<n;i++)
    {    
      if(dp[i]>max)
        max=dp[i];   
    }
  
  printf("%d",max);  
  
}