[BaekJoon] 11053 가장 긴 증가하는 부분 수열 (Java)

🔗 문제 링크

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

📝 문제 풀이 방법

이번 문제는 순열 중에서 값이 증가하는 부분 순열 중에서 길이가 가장 긴 순열을 구하는 문제이다.

문제의 Dynamic Programming의 방식으로 해당 값까지 넣었을 때 생성되는 수열의 길이를 나타내는 정보를 가진 배열을 만들고 진행한다.

코드는 이전에 위치한 수들과 비교를 하여 현재의 수가 이전의 수보다 크기가 크고 해당 수의 배열의 값+1이 현재 자신의 수보다 크다면 값을 업데이트 하는 방법으로 진행이 된다.

👨🏻‍💻 작성한 코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		
		int count = 0;
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] dp = new int[n];
		Arrays.fill(dp, 1);
		
		
		for (int i=0; i<n; i++) {
			for (int j=0; j<i; j++) {
				if (arr[j]< arr[i]) {
					dp[i] = dp[i] < dp[j]+1? dp[j] +1: dp[i];
				}
			}
		}

		Arrays.sort(dp);
		System.out.println(dp[n-1]);
	}

}