[PS] BOJ11053 가장 긴 증가하는 부분 수열 ( LIS ) With Python,JAVA

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

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

 

 

◎ 문제풀이

 

DP는 수열에서 나올 수 있는 부분수열의 모든 경우에서 조건에 맞는 경우를 구하는 문제이다. 이때, 부분수열의 조건이 '가장 길고'(Longest) '증가하는'(Incresing) 부분수열(Subsequence)를 구하는 문제라면,  LIS( Longest Increasing Subsequence) 알고리즘 풀이라 생각하면 된다.

 

 

 

 

5번째 50일때, 가장 긴 부분수열은 어떻게 만들어질까? 경우를 따져보자.

 

1) 0번째 부분수열 

2) 0번째-1번째 부분수열

3) 0번째-2번째 부분수열

4) 0번째-3번째 부분수열

5) 0번째-4번째 부분수열 

 

5가지 경우 중 50보다 작은 부분수열로 이루어진 경우에서 최댓값을 구하면 된다.

 

 

 

최댓값을 빠르게 구하려면 각 경우도 가장 긴 부분수열을 저장해놓아야 한다. ( 메모리제이션 )

 

1) 0번째 부분수열 : 1

2) 0번째-1번째 부분수열 : 2

3) 0번째-2번째 부분수열 : 1

4) 0번째-3번째 부분수열 : 3

5) 0번째-4번째 부분수열 : 2

 

5가지 경우는 모두 50보다 작고 최댓값은 3이다. 그럼 5번째 50에서의 가장 긴 증가하는 부분수열은 3+1, 4가 된다. 이처럼 DP 풀이는 n이 만들어지는 n-1의 경우를 추려 점화식을 만들고 각 경우를 메모리제이션으로 저장하여 빠르게 문제를 푸는 방법이다.

 

 

◎ 코드

 

Python

#BOJ11053 가장 긴 증가하는 부분수열

n = int(input())
arr = list(map(int,input().split()))
dp = [0] * n # DP 테이블

for i in range(n) :
  for j in range(i) :
    if arr[i] > arr[j] : # 증가하는 부분수열
      dp[i] = max(dp[i],dp[j]) # 최댓값 저장
  dp[i] += 1

print(max(dp))

 

JAVA

public class Main {

    public static void main2(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[] arr = new int[n+1];
        int[] dp = new int[n+1];

        for(int i =1;i<n+1;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int maxLength = 0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]){
                    dp[i] = max(dp[i],dp[j]);
                }
            }
            dp[i]++;
            maxLength = max(maxLength,dp[i]);
        }
        System.out.println(maxLength);
    }
}