[백준] 11053 - 가장 긴 증가하는 부분 수열 (자바/Java)

문제 링크

성능 요약

메모리: 16964 KB, 시간: 192 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 A_i가 주어진다. (1 ≤ A_i ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

가장 긴 증가하는 부분 수열 (LIS)를 구하는 문제다.

여러 가지 방법이 있지만 입력이 1000 이하기 때문에 $O(n^2)$의 시간복잡도를 가지는 알고리즘을 사용해도 충분하다.

 

https://rebro.kr/33

LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열

위 블로그에 LIS를 구할 수 있는 다양한 알고리즘이 소개되어 있다.

 

내가 사용한 방법은 첫 번째 방법으로 이중 for문으로 dp값을 찾는 것이다.

 

		for (int i = 1; i < N; i++)
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i])
					// i번째를 포함할지 안할지
					dp[i] = Math.max(dp[j] + 1, dp[i]);
			}

i는 현재의 index, j는 i보다 왼쪽에 있는 index를 의미한다.

10 20 10 30 20 50

위와 같이 수열이 이루어졌다고 가정할 때, 

LIS를 구하는 과정은 다음과 같다.

 

i의 값이 j의 값보다 크면, dp[i]와 dp[j]+1의 값을 비교해서 dp값을 결정한다.

i가 j보다 크다고 해서 i를 포함하는 게 최장 길이가 아닐 수도 있기 때문에, i보다 index가 작은 값을 모두 검토하여 가장 긴 길이를 구하는 과정이다.

 

전체 코드

package Silver.s2;

import java.util.Arrays;
import java.util.Scanner;

public class BOJ_11053_LIS {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int[] arr = new int[N];

		for (int i = 0; i < N; i++)
			arr[i] = sc.nextInt();
		int[] dp = new int[N];
		Arrays.fill(dp, 1);

		for (int i = 1; i < N; i++)
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i])
					// i번째를 포함할지 안할지
					dp[i] = Math.max(dp[j] + 1, dp[i]);
				
			}
		int ans = 0;
		for (int i = 0; i < N; i++)
			ans = Math.max(dp[i], ans);
		System.out.println(ans);

	}

}