[백준] 11053 가장 긴 증가하는 부분 수열 - Dynamic Programming / Java

• 문제 링크

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

 

• 풀이 과정

입력받은 수열을 arr 배열을 생성해 저장하고, 각각의 부분 수열의 길이를 메모이제이션할 dp 배열을 생성,

2중 for문으로 배열의 현재 인덱스와 이전 인덱스들을 비교하며 탐색을 진행한다.

 

기본적으로 수열의 최소 길이인 1로 dp 배열의 인덱스를 초기화한다.

증가하는 부분 수열이므로 비교하고자 하는 arr 배열 값보다 현재 값이 크고,

dp 배열에 현재까지 갱신된 부분 수열의 길이가 비교하고자 하는 부분 수열의 길이보다 같거나 작을 시

현재 dp 배열 인덱스에 비교한 인덱스의 길이에 1 증가된 값을 대입한다. 

 

이를 구현하기 위한 조건문은 arr[j] < arr[i] && dp[i] <= dp[j] 이며 이에 따른 값 변화를 나타내면 아래와 같다.

arr	10	20	10	30	20	50
부분 수열	{10}	{10, 20}	{10}	{10, 20, 30}	{10, 20}	{10, 20, 30, 50}
dp	1	2	1	3	2	4

이때 dp[i] <= dp[j] 이 필요한 이유는 예시로 arr[3] = 30, dp[3] = dp[0] + 1 = 2 의 시점에서 이전 인덱스와 비교 시,

이미 arr[1] = 20 와 비교하여 dp[3] = dp[1] + 1 = 3 의 부분 수열 길이를 구했음에도

이어서 arr[2] = 10 과 비교하여 dp[3] = dp[2] + 1 = 2 로 부분 수열의 길이가 갱신되지 않기 위함이다.

 

이렇게 각각의 최장 부분 증가 수열이 구해질 때마다 max 변수에 가장 큰 값을 갱신시켜 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		int[] dp = new int[n];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		
		int max = 0;
		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])
					dp[i] = dp[j] + 1;
			}
			
			max = Math.max(max, dp[i]);	
		}

		bw.write(max + "\n");
		bw.flush();
	}

}