[JAVA] BOJ 11053 가장 긴 증가하는 수열

 

 

동적 계획법 문제답게 메모이제이션과 점화식을 생각해봐야 한다.

 

A= {10, 20,10, 30, 20, 50} 라면 F(N) 은 N번째 요소가 이전 요소 중 몇 번째로 증가하는 수열인지 저장한다. 즉, 3번째 요소인 10은 이전 값 {10, 20} 중 1번째로 증가하는 수열이기 때문에 1이 F(3) = 1이 된다. 이처럼 A의 모든 요소를 반복문으로 돌면서 F(N) 값을 저장한 뒤 출력할 때는 F(N) 중 가장 큰 값을 출력하면 된다.

 

코드로 보면

import java.io.*;
import java.util.*;

public class Main {
	public static Integer[] DP;
	static ArrayList<Integer> cost = new ArrayList<>();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int max= 0;
		int N = Integer.parseInt(br.readLine());
		DP = new Integer[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			cost.add(Integer.parseInt(st.nextToken()));
		}
		
		for(int i=0; i<N;i++) LIS(i);
		
		for(int i: DP) max = Math.max(max, i);
		System.out.println(max);
	}
	
	public static int LIS(int N) {
		if (DP[N] == null) {
			DP[N] =1;
			for(int i =N-1;i>=0;i--) {
				if(cost.get(i)<cost.get(N)) {
					DP[N] = Math.max(DP[N], LIS(i)+ 1);
				}
			}
		}
		return DP[N];
	}
}

 

DP 배열은 F(N) 값을 저장하는 배열이고, cost배열은 입력값이 주어지는 배열이다. LIS 메서드는 요소의 위치를 N이라는 매개변수로 전달받아 DP [N]의 방문 여부를 확인하고 방문하지 않았다면 1로 초기화를 한다. 모든 요소는 우선적으로 첫 번째로 증가하는 수열이기 때문이다. 

이어서 해당 요소가 몇 번째로 증가하는 수열인지 확인하기 위해서 이전 요소들과 대소 비교를 해야 한다. 대소 비교만 하는 것이 아니라 증가하는 수열 길이도 비교해야 한다. 예를 들어 A={10, 10, 20}이라면 마지막 요소인 20은 첫 번째 요소와 두 번째 요소보다 크지만 첫 번째 요소와 두 번째 요소는 크기가 같기 때문에 20의 증가하는 수열 길이는 2가 된다.

 

모든 요소의 증가하는 수열 길이를 DP 배열에 저장했다면 DP배열 중 최댓값(max)을 출력하면 된다.