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

www.acmicpc.net/problem/14002

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

 

1. 문제 설명

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하고 가장 긴 증가하는 부분수열의 길이와 가장 긴 증가하는 부분 수열을 출력하는 문제이다.

 

먼저 dp배열을 사용하여 현재 위치를 포함하여 만들 수 있는 가장 긴 증가하는 부분수열의 길이를 저장하였다.

그리고 cache 배열을 사용하여 현재 위치에서 가장 긴 증가하는 부분 수열을 만들기 위해서 선택한 인덱스의 위치를 저장한다.

 

dp 배열을 사용하여 수열 길이의 최대값, 수열 A에서 가장 긴 부분 수열이 끝나는 위치를 찾는다.

그 다음, cache 배열을 이용하여 선택을 역추적, 이를 출력하면 되는 문제이다.

 

2. 코드

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {

    public static int n;

    public static int[] list=new int[1001];
    public static int[] dp=new int[1001];
    public static int[] cache=new int[1001];

    public static void main(String[] args) throws IOException {

        Scanner scan=new Scanner(System.in);

        n=scan.nextInt();

        int max=0;
        int max_index=0;

        for(int x=0;x<n;x++){
            list[x]=scan.nextInt();
            dp[x]=1;

            for(int y=0;y<x;y++){
                if(list[y]<list[x] && dp[y]+1>dp[x]){
                    dp[x]=dp[y]+1;
                    cache[x]=y;
                }
            }

            if(dp[x]>max){
                max=dp[x];
                max_index=x;
            }
        }

        int [] answer=new int[max];
        int index=max_index;

        for(int x=max-1;x>=0;x--){
            answer[x]=list[index];
            index=cache[index];
        }

        System.out.println(max);
        for(int x=0;x<max;x++)
            System.out.print(answer[x]+" ");


    }




}