[SWExpertAcademy]3307번 최장 증가 부분 수열 - Java

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr 

SW Expert Academy

 

 

풀이

유명한 DP 문제 유형이라고 한다.

 

DP말고 부분 집합으로도 풀 수 있다. 하나하나 첨부터 끝까지 부분집합을 만들어서 가장 긴 증가하는 부분 수열을 뽑아내도 되는데 그렇게 하면 O(2^N)의 시간 복잡도가 소요된다. 개오래 걸리는거지 미친거지 그니깐

물론 뭐 공집합부터 탐색하는게 아니라 전체집합부터 탐색하면 조금 더 빨리 찾을 수는 있겠지만,,,

 

그니까 부분 집합말고 DP로 풀어야 시간 초과가 안나겠지???

1차원 배열을 만들어서 for문을 두번 돌면서 첫 원소부터 현재 원소까지 비교하면서 1차원 배열에 갱신할지 말지 정해서 증가하는 수열이면 갱신해준다 -> 이렇게 쭈욱 진행하면 됨!

 

자세한건 주석 참고!

 

 

코드

// 3307 - 최장 증가 부분 수열

package d3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Num3307_최장증가부분수열 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            int N = Integer.parseInt(br.readLine()); // 수열의 크기

            int[] arr = new int[N]; // 수열의 원소를 저장
            int[] dp = new int[N]; // 자신을 끝으로 하는 LIS 길이

            Arrays.fill(dp, 1); // 자신 혼자 LIS 구성할 때의 길이 1로 초기화

            st = new StringTokenizer(br.readLine());

            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            int max = 1; // 해당 수열의 LIS 최장 길이
            for (int i = 0; i < N; i++) { // 모든 원소에 대해 자신을 끝으로 하는 LIS 길이 계산
                for (int j = 0; j < i; j++) { // 첫 원소부터 i원소 직전까지 비교
                    if (arr[j] < arr[i] && dp[i] < dp[j] + 1) { // arr[j] < arr[i]: 증가 수열의 모습인지 확인
                        dp[i] = dp[j] + 1;
                    }
                }

                max = Math.max(max, dp[i]);
            }

            System.out.println("#" + t + " " + max);
        }
    }
}