[백준/11053] 가장 긴 증가하는 부분 수열 (Java/코드)

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

가장 긴 증가하는 부분 수열 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	25765	9459	6448	37.169%

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 

6
10 20 10 30 20 50

예제 출력 1 

4

---

확실히 비슷한 코드를 반복해서 풀다보니, 아주 조금이나마 동적 프로그래밍 알고리즘에 대해 이해가 되어가고 있다.

얼른 dp를 마무리 짓고, 다음 단계도 반복해서 풀어 나아가야겠다!

이 경우에는 증가하는 수열을 골라야해서, 수열을 저장하는 배열 a[] 과, 수열의 길이를 저장하는 배열 d[]를 같이 비교해야한다.

    0   1   2  3  4   5

a[] 10 20 10 30 20 50 

d[] 1   2   1   3  2  4

이런 방식으로 생각해서 풀면 생각해야할 조건은 두가지이다.

1. i번째 오는 배열은 0~ i-1 까지의 배열을 한번씩 다시 돌아서 체크해야한다.

2. a[ i-1 ] < a[ i ] 

   증가하는 수열이지만, i-1 보다 i-2가 더 큰 수열의 길이일수도 있다.

   ex ) d[1]은 2로 저장되었고, a[2] < a[3] 이지만, d[2]는 1이므로, d[2]+1이 d[3]로 저장되어서는 안된다.

import java.util.*;
public class Main{
 
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int max=0;
        int[] d = new int[n+1];
        int[] a = new int[n+1];
 
        for(int i=0; i<n; i++){
            a[i]=sc.nextInt();
            d[i]=1;
        }
    
        for(int i=0; i<n ; i++){
            for(int j=0 ; j<=i ; j++){
                if(a[j]<a[i] && d[j]>=d[i]){
                    d[i]=d[j]+1;
                }
            }
        }
        
        for(int i=0; i<n ; i++){
            if(d[i]>max)
                max=d[i];
        }
 
        System.out.println( max );
        
    }  
}