[JAVA]백준 11053번: 가장 긴 증가하는 부분 수열

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

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

 

 

 

 

 

 

요즘엔 DP를 중점적으로 공부하고 있기 때문에, DP관련 문제들만 찾아서 풀고 있다. 

오늘은 그 중에서 '11053_가장 긴 증가하는 부분 수열'과 '11722_가장 긴 감소하는 부분 수열' 두 문제를 풀어보았다. 

 

 

 

| 문제 해결방법

 

 

관련 알고리즘 : 최장 증가 부분 수열(LIS) + DP

 

 

주어진 요소들 중에서 조건에 맞는 원소들을 선택할 수 있는 최대 길이를 구하는 문제이다. 

 

 

 

 

순서는

 

LIS()를 arr배열 첫 번째 원소부터 마지막 원소까지 돌린다. 

 

 

 

LIS(int N) 메서드 안에서는

 

우선 아직 탐색하지 않은 요소라면

dp[N]에 자기 자신을 count한 값인 1을 넣어준다.

 

그리고

현재 인자로 전달받은 N(index)를 이용해서

arr[N]과 arr[N-1]~arr[0]까지 비교를 통해 arr[N]보다 작은 값(=i)을 찾으면 

dp[] 배열에 메모제이션을 해준다.

 

메모제이션은 

dp[N] = Math.max(dp[N], LIS(i)+1) 로

현재 저장되어 있는 값과 조건에 맞는 이전 값 중 최대 값 + 1 을 비교하여 큰 값을 저장한다.

 

 

[JAVA] 해설 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int[] arr;
	static int[] dp;
	static int A;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		A = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr = new int[A];
		dp = new int[A];
		
		//Arrays.fill(dp, -1);
		for(int i=0;i<A;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		
		for(int i=0;i<A;i++) {
			LIS(i);
		}
		
		int max = -1;
		for(int i=0;i<A;i++) {
			max = Math.max(max, dp[i]);
		}
		System.out.println(max);
		
	}
	private static int LIS(int N) {
		// 탐색하지 않았던 위치의 경우
		if(dp[N]==0) {
			dp[N]=1; // 1로 초기화
			
			for(int i=N-1;i>=0;i--) {
				if(arr[N] > arr[i]) {
					dp[N] = Math.max(dp[N], LIS(i)+1);
				}
			}
		}
        
		return dp[N];
		
	}
	
}

 

 

[제출] 메모리 및 시간