[SWEA] 3307. 최장 증가 부분 수열

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

---

접근 방법

DP로 풀었다. N+1 크기의 숫자 배열과 N+1 크기의 DP 배열을 사용했다.

왼쪽부터 차례로, 해당 값이 왼쪽 값보다 클 경우 해당 값의 DP와 왼쪽 값의 DP+1 중 더 큰 값을 해당 값의 DP에 저장했다.

숫자 배열의 처음 값은 0이므로 단번에 해당 값을 포함할 때의 최대 길이를 저장할 수 있다.

그래서 매번 전체 최대 길이도 갱신했다.

 

소스 코드

import java.util.*;
import java.io.*;
 
class Solution {
    static int[] dp;
    static int[] num;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int T = sc.nextInt();
        for(int t=1; t<=T; t++) {
            int N = sc.nextInt();
            dp = new int[N+1];
            num = new int[N+1];
             
            for(int i=1; i<=N; i++)
                num[i] = sc.nextInt();
             
            int val = 0;
            for(int i=0; i<=N; i++) {
                for(int j=0; j<i; j++) {
                    if(num[i] > num[j]) {
                        dp[i] = Math.max(dp[i], dp[j]+1);
                        if(val < dp[i])
                            val = dp[i];
                    }
                }
            }
            System.out.println("#" + t + " " + val);
        }
    }
}