[BAEKJOON]11722 가장 긴 감소하는 부분 수열

문제 요약

• 알고리즘 분류: dp, LIS
• 난이도:  Silver2
• 문제내용:
  • 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.
  • 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

• 사이트: https://www.acmicpc.net/problem/11722

문제풀이

 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하 O(N^N)개 이상으로 나올수 있다. 그래서 이번 문제는 LIS 개념을 적용해서 풀어야 한다. LIS에 대한 개념은 아래 글에서 확인 해보면된다.

https://jih3508.tistory.com/46

[알고리즘 이론] LIS(Longest Increasing Subsequence) 최장 증가 부분 수열

 이번 문제는 LIS 기초 개념만 알면 푸는데는 지장 없어서 따로 설명 안하겠다.

Code

 LIS중 데이터 양이 최대 1000개라서 DP로 풀수 있어서 간단하게 DP로 했다.

Python

N = int(input())
A = list(map(int, input().split()))

# 모든 dp 배열 1로 초기화
dp = [1] * N

for i in range(1, N):
    for j in range(i):
        if(A[i] < A[j]):
            # 이전 값들과 비교해서 큰 값이면 이전 저장 되는 것과 수열 개수 비교
            dp[i] = max(dp[i], dp[j] + 1)

# dp 배열중 가장 길게 저장 된 결과 값을 가져온다.
print(max(dp))

Java

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());

		int[] nums = new int[N];
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}

		int[] dp = new int[N];
		// 모든 dp 배열 1로 초기화
		Arrays.fill(dp, 1);
		for (int i = 1; i < N; i++) {
			for (int j = 0; j < i; j++) {
				// 이전 값들과 비교해서 큰 값이면 이전 저장 되는 것과 수열 개수 비교
				if(nums[i] < nums[j]){
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}

		System.out.println(Arrays.stream(dp).max().getAsInt());

	}
}