3307. 최장 증가 부분 수열

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

SW Expert Academy

 

문제 해석

 

어떤 수열의 증가하는 수열의 최대 크기를 찾으면 됩니다.

 

수열
1 3 2 5 4 

정답 : 3

해석 : 1 -> 2 -> 4 또는 1-> 2 -> 5 또는 1 -> 3 -> 5 또는 1 _> 2 -> 4 의 최댓값은 3

 

수열

4 2 3 1 5 6

정답 : 4

해석 : 2 -> 3 -> 5 -> 6 

 

 

문제 풀이 전 설계

DP를 활용하여 DP[i]에는 현재 i 값이 마지막으로 오는 최장 부분 수열을 기록합니다.

모든 원소의 자기 자신의 길이는 1이므로 DP[i]는 모두 1으로 시작합니다.

 

i번째 수부터 검사합니다. (i = 2부터 시작합니다)  : 이유는 맨앞의 원소는 비교할 값이 없어서 항상 최장 부분 수열이 1

1~j번째 수를 검사하며 DP[i] 보다 DP[j]+1이 크다면 갱신합니다. ( j는 1~j-1)까지 반복합니다.

 

코드

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

public class Solution_최장증가부분수열 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        int result;
        int[] dp = null;
        int[] nums = null;
        StringTokenizer st =null;
        for(int tc=1 ; tc<=T; tc++){
            result = 0;
            int length =  Integer.parseInt(br.readLine());
            dp = new int[length+1];
            //자기 자신의 길이는 1이므로 모두 최장 증가 부분 수열을 1로 시작합니다.
            Arrays.fill(dp,1);

            st = new StringTokenizer(br.readLine(), " ");
            nums = new int[length+1];
            for(int i=1; i<=length; i++){
                nums[i] = Integer.parseInt(st.nextToken());
            }

            //입력끝

            //2번째 수부터 검사
            for(int i=2; i<=length; i++){
                //1번째 수부터 i번째 전까지
                for(int j=1; j<i; j++){
                    //검사하는 값보다 이전에 있는 값들이 크면 증가할 수 없음
                    if(nums[j] >= nums[i]){
                         continue;
                    }
                    //검사하는 값보다 이전에 있는 값들이 작으면 증가할 수 있음
                    dp[i] = Math.max(dp[i],dp[j] +1 );
                }
            }

            //최장 증가수열 탐색
            for(int i=1; i<=length; i++){
                result = Math.max(dp[i],result);
            }

            sb.append("#" + tc + " " + result + "\n");

        }
        System.out.println(sb.toString());
    }
}