[백준]11053번 가장 긴 증가하는 부분 수열(java)

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

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

백준 11053번 가장 긴 증가하는 부분 수열 문제 링크입니다.

핵심

동적 계획법을 사용하여 푸는데, 증가하는 수열을 만들 때, 가장 큰 길이를 구하는 것이다. 그전 값을 비교하며 더 커지면 dp를 증가시키는 형태이다.

 

정답 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        int[] dp = new int[N];

        for (int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }
        for (int i=0; i<N; i++){
            dp[i] = 1;
            for (int j=0; j<i; j++){
                if (arr[j]<arr[i]&&dp[i]<dp[j]+1){
                    dp[i]=dp[j]+1;
                }
            }
        }
        int max = 0;
        for (int i = 0;i<N; i++){
            max = Math.max(max,dp[i]);
        }
        System.out.println(max);
    }
}

 해설

N크기의 arr와 dp배열을 만든다. 

arr에 우리가 원하는 값들을 넣어준다.

dp에 1을 넣어주면서, 반복문을 실행하는데, arr 값이 그전보다 크고,

dp에 저장된 값이 그전의 값에서 1을 더한 값 보다 작으면 dp에 그 전 dp에서의 +1을 해준다.

이후 max를 구한다.

 

 

개선점이나 오류가 있다면 댓글 부탁드립니다.