[JAVA]백준 11053 가장 긴 증가하는 부분 순열

JAVA로 풀이했습니다.
출처 : 백준 알고리즘 https://www.acmicpc.net

문제 개요

11053번 문제 👉 https://www.acmicpc.net/problem/11053
수열 A의 가장 긴 증가하는 부분 수열의 길이
난이도 👉 실버 2

풀이과정

처음에는 부분집합으로 접근했습니다. 가장 긴 증가하는 부분 수열을 만들기 위해서 증가하는 원소를 가진 부분 집합을 만들려고 했습니다. 하지만 시간 복잡도에서 O(2^N)이 나오므로 주어진 시간 안에 해결하는 것은 불가능합니다.

두번째로 접근한 방법은 Dynamic Programming을 통해 접근했습니다. 왜냐면 N이 최대 1000이므로 O(NlogN)이 되도록 코드를 작성하였습니다.

나만의 방법

먼저 DP배열에 1000가지의 공간을 미리 만들고 1부터 N까지 순차적으로 계산한다. 이때 두가지 조건을 모두 만족시켜야한다. 비교 대상 숫자의 이전값들을 비교하며 증가하는지 확인한다. 그리고 이전까지의 최대 길이(DP배열에 저장된 최대값)를 계속 업데이트해준다. 마지막 비교 시에 증가한다면 이전까지의 최대값보다 1이 더 긴 증가 수열임을 확인할 수 있다.

소스코드

import java.util.Arrays;
import java.util.Scanner;

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

		//N is array size, arr is array with size N
		N = sc.nextInt();
		arr = new int[N+1];

		//input
		for(int i=1;i<=N;i++) {
			arr[i] = sc.nextInt();
		}

		//variable initialization
		answer = 0;
		dp = new int[1001];

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