백준 11053 가장 긴 증가하는 부분 수열 Java

굉장히 유명한 문제라고 한다. 정답률은 37퍼센트 이다.

다이나믹으로 안풀어도 될 것 같아서 시도했다가 수 많은 반례에 짓밟혔던 문제이다.

최대값이 꼭 배열의 마지막에 있는 것이 아닌

10 50 10 20 30 40 이런식으로 예제가 입력 되는 경우도 있기 때문에

다이나믹 프로그래밍으로 풀어야 한다.

 

이 문제는 dp배열에 i번째에서의 길이를 넣어주면 된다.

10 20 10 30 20 50 이면

dp[1] (20)은 2이고

dp[3] (30)은 3이다.

숫자가 하나만 있어도 길이는 1이기 때문에 dp배열은 전부 1로 초기화 한다.

 

반복문 2개로  수열[i]보다 작은 범위의 수열[j]를 훑어서 수열[i]보다 값이 작으면

dp[j]를 본다. dp[j]가 dp[i]보다 값이 크거나 같다면. dp[i] = dp[j]+1 을 해주면 된다.

 

그 후 

dp배열 중 가장 큰 값을 출력하면 된다.

글로 설명하는 것보다 코드를 보는게 더 이해가 잘될 것 같다.

 

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int []a = new int[n];
        int []dp = new int[n];
        
        for(int i=0; i<n; i++)
            a[i] = scan.nextInt();
        
        for(int i = 0; i<n; i++) {
            dp[i] = 1;
            for(int j=0; j<i; j++)
                if(a[i]>a[j] && dp[i]<=dp[j]) 
                    dp[i] = dp[j]+1;
        }
        Arrays.sort(dp);
        
        System.out.println(dp[n-1]);
            
    }