Yong's Tech Story

문제 풀이 (JAVA)

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

public class Main {
	/**
	 * 숫자가 이전 값보다 큰 경우, (현재 값)보다 (이전 값) +1이 크다면 변경
	 * 
	 * @param args
	 * @throws IOException
	 */
	public static void main(String[] args) throws IOException {
		// 최대 부분 증가 수열(LIS)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int[] arr = new int[N];
		int[] dy = new int[N]; // 각 숫자마다 현재 최대 수열
		int max = 0;

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			dy[i] = 1;
		}

		for (int i = 1; i < arr.length; i++) {
			for (int j = i - 1; j > 0; j--) {
				// 현재 값 기준으로 앞에 값이 현재값 보다 작다면
				if (arr[i] > arr[j]) {
					// 숫자가 이전 값보다 큰 경우, (현재 값)보다 (이전 값) +1이 크다면 변경
					dy[i] = Math.max(dy[i], dy[j] + 1);
					max = Math.max(max, dy[i]);
				}
			}
		}
		System.out.println(max);

	}

}

정리

1. 해당 문제는 랜덤한 숫자가 있을시 가장 긴 부분수열을 찾는 문제로 처음에는 투포인터나 DFS 문제인줄 알았으나 LIS 알고리즘을 사용하는 DP문제임을 알게 되었다.

2. 들어오는 숫자 배열마다 최대 부분수열을 각 배열(dy)로 저장하며, 현재 숫자를 기준으로 앞의 숫자들과 비교하여 더 작은 숫자가 있을시, 해당 숫자의 부분수열(dy[]) 값의 +1 증가한 값으로 현재 dy 배열을 저장한다.

3. 이 문제에서 중요한 부분은 현재 배열의 숫자가 이전값보다 크다면, 해당 값들만 dy 값을 비교하여 현재 배열들을 채워나가는 형식이다.

4. 주의 할 점은 마지막 배열이 작은 값이 들어와 이전 값보다 작아 비교가 안되는 경우가 있으니, 마지막 값이 가장 긴 부분수열이 되리라는 보장이 없다.