[SWEA D3] 3307. 최장 증가 부분 수열 : JAVA 풀이

문제 - 3307. 최장 증가 부분 수열

swexpertacademy 문제 바로가기 (로그인 후 이용가능)

설명

먼저 LIS 문제는 DP로 푸는 것으로 공부했기 때문에
저장된 배열을 가지고 dp 배열을 만들어 i번째 dp값과 저장된 max값 중 최댓값을 도출한다.

1. dp배열의 처음 값은 길이니까 1이 된다.
2. 1번째 인덱스부터 이중포문을 돌면서 그 전의 원소까지 dp값들을 1로 초기화한다.
3. 배열의 원소값이 전 원소보다 크고 이전 dp값이 1보다 크거나 같으면 i번째 dp값을 증가시킨다.
4. max값을 업데이트한다.

자바 풀이

import java.util.*;



public class Solution {

    static int n;
    static int max;
    static int[] arr;
    static int[] dp;
    static StringBuffer sb = new StringBuffer();

    public static void main(String[] args) throws Exception {

        //LIS

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {

            max = 1;
            
            n = sc.nextInt(); //수열의 길이

            arr = new int[n];
            dp = new int[n];

            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }

            dp[0] = 1;
            for (int i = 1; i < n; i++) {
                dp[i] = 1; //기본값 1 초기화
                for( int j=0;j < i;j++) { //현재위치-1 까지 작은 값
                    // 원소값이 전원소보다 크고, 전 dp값이 1보다 크거나 같으면
                    if (arr[j] < arr[i] && dp[i] <= dp[j])
                        dp[i] = dp[j] + 1;
                }
                max = Math.max(max, dp[i]);
            }

            sb.append("#" + tc).append(" ").append(max).append("\n");
        }
        System.out.println(sb);
    }

}