백준 14002번: 가장 긴 증가하는 부분 수열 4

주어진 수열에서 가장 긴 증가하는 부분 수열을 고르는 문제이다.

 

 

INPUT

6

10 20 10 30 20 50

 

OUTPUT

4

10 20 30 50

 

INPUT

5

3 4 1 2 3

 

OUTPUT

3

1 2 3

 

www.acmicpc.net/problem/11053

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

위의 문제는 최댓값만 구하는 문제이고, 이번 문제는 최댓값과 수열을 같이 구하는 문제로 조금 더 응용이 필요하다.

 

6

10 20 10 30 20 50 

 

문제를 풀기 위해서는 수열을 부분 부분 잘라서 값을 확인해야 하며 두 가지의 배열이 더 필요하다.

 1) 각각의 원소까지만 보았을 때, 가장 긴 최댓값을 넣는 배열 (dp)

   - dp [i] 에는 i 번째 원소가 가질 수 있는 부분 수열의 최대 길이.

 2) 바로 이전의 순서를 기록하는 배열 (v)

   - 첫 번째 자리일 경우에는 -1이다. 조건에 맞는 경우가 생기면, 작은 수의 배열을 넣어주도록 한다.

 

위의  두 가지 배열을 만들어서 값을 기록하도록 한다.

 

 

1)       arr 배열         10 

 최댓값 dp배열          1

 전 기록 v 배열         -1

 => 10

 

2)         arr배열        10     20 

 최댓값  dp배열         1      2 

 전 기록 v 배열         -1      0

 => 10 -> 20

 

3)         arr배열       10     20    10

 최댓값  dp배열        1      2      1

 전 기록 v 배열         -1     0     -1

 => 10 -> 20 

 

4)          arr배열       10     20    10    30 

 최댓값   dp배열        1      2      1      3

 전 기록 v 배열         -1      0     -1     1

 => 10 -> 20        or    10 -> 30

 

5)          arr배열       10     20    10    30    20

 최댓값   dp배열        1      2      1      3     2

 전 기록 v 배열         -1      0      -1     1     2

 => 10 -> 20        or    10 -> 30

 

6)          arr배열       10     20    10    30    20    50

 최댓값   dp배열        1      2      1      2     2     3

 전 기록 v 배열         -1      0      -1     1     2    4

 => 10 -> 20  -> 30  ->  50

 

 

import java.lang.Math; 
import java.io.*;
import java.util.*;
public class Main{
  public static int[] arr;
  
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    arr = new int[n+1];
    
	for(int i=0;i<n;i++){
         arr[i] = sc.nextInt();
      
    }
   
    int dp[] = new int[n];
    int v[] = new int[n];
    for (int i = 0; i < n; i++) { // 1 번
        dp[i] = 1;
        v[i]=-1;
        for (int j = 0; j < i; j++) { // 2 번
            if (arr[j] < arr[i] && dp[i] <=dp[j] + 1) { // 3 번
                dp[i] = dp[j] + 1;  // 4번
              	v[i] = j;	
            }  
        }
    }
    int idx = 0;
    for(int i=1;i<n;i++) {
    	if(dp[i]>dp[idx])
    		idx = i;
    }

    System.out.println(dp[idx]);
    output(v,idx);

    System.out.print(arr[idx]);
  }
  
  public static void output(int[] v,int n){
    
    if (v[n] ==-1)
    	return;
	output(v,v[n]);
	System.out.print(arr[v[n]]+" ");
    
  }
  
}
  

 

구현 순서는 이렇게 된다.

1. 해당 수열을 부분 자른다.

2. 부분 수열의 맨 마지막 원소와 앞의 원소들을 하나씩 비교하며 증가하는지 판단한다.

3. 증가하는 경우라면, 비교한 원소 최댓값 + 1 이 맨 마지막 원소의 최댓값이 될 것이다.

 - 이 때, 증가하는 다른 원소의 최댓값 + 1이 더 큰 값인지 아닌지도 판단한다.

4. 위의 경우에 모두 해당될 경우, dp 배열의 최댓값은 1이 증가할 것이고,

 v 배열에는 해당하는 수열 중 바로 앞 원소 인덱스를 담아, 증가하기 직전의 원소가 몇 번 째인지를 표시한다.

 

 

출력을 할 때에는 재귀나 스택 등을 이용해야 한다.

 

dp 배열을 이용해 최댓값인 idx를 골라서 최댓값을 출력해준 후,

 

v [idx]부터 타고 들어가서 -1이 나올 때까지 재귀로 찾아 준 후, 그 값부터 출력해주도록 한다.