백준 11053 - 가장 긴 증가하는 부분 수열 (JAVA 풀이)

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

 

 

 

이 문제는 전체 수열을 하나하나 탐색해서 증가하는 수열 중 가장 긴 수열의 길이를 찾아내야 된다. 

for문을 두번 돌려서 현재 나의 위치에 들어있는 값(arr[i])과 비교를 할 값을(arr[j]) 확인해보고, 

나의 위치에 들어있는 값이 비교할 값보다 더 크다면 패스하고, 작다면 DP배열을 업데이트 하는식으로 진행하면 된다. 

DP를 사용해야 되는데, 내가 참고한 블로그는 아래 링크를 통해 들어가면 된다. 

설명을 아주 이해하기 쉽게 해주셨다. 

 

참고한 블로그 : https://sskl660.tistory.com/89

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class LIS {
 
    static int N;
    static int [] dp, arr;
 
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine()); // 6
 
        dp = new int[N+1];
        arr = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++){
            arr[i] =  Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }
 
        // dp 알고리즘 구현
 
        for (int i=1; i<=N; i++){
            for(int j=1; j<i; j++){
                if (arr[i] > arr[j]){ // 더 큰 수가 들어있다면
                    dp[i] = Math.max(dp[j]+1, dp[i]);
                }
            }
        }
 
        int MAX = -1;
 
        for(int i=1; i<=N; i++){
            MAX = Math.max(dp[i], MAX);
        }
 
        System.out.println(MAX);
    }
 
}