[JAVA] 백준 11053 가장 긴 증가하는 부분 수열

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

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

 

- 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램

 

ex) 수열 A ={10,20,10,30,20,50}

- 가장 긴 증가하는 부분 수열은 A={10,20,10,30,20,50}이고, 길이는 4

 

문제 풀이 

 

[알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java) (tistory.com)

[알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java)

 

[백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바] (tistory.com)

[백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바]

가장 긴 증가하는 부분 수열 (LIS)

- LIS(Longest Increasing Subsequence)는 불연속 상관없이 가장 긴 증가하는 부분 수열을 구하는 알고리즘 

- 주어진 '수열'에서 일부 원소를 뽑아내어 새로만든 수열이 '부분 수열'

- 이 수열이 '오름차순'인 수열이 '증가하는 부분 수열'이 된다. 

- 만들 수 있는 오름차순 수열 중, '가장 긴' 수열이 LIS가 된다.

 

- 풀이 방법으로는 DP를 활용한 LIS, 이진 탐색을 활용한 LIS 두가지가 있다. 

 

 DP로 풀이하는 방법 

 

 - O(N^2)

 - dp는 1차원 배열로 dp[i]에는 0~i 증가하는 부분 수열의 크기를 나타냄 

 

 - 이중 반복문을 설계하여 각 수를 직접 비교해가면서 증가하는 부분 수열의 크기를 카운트 해준디

 - 가장 긴 증가하는 부분 수열 LIS는 dp[i] 중 최댓값을 선택해 출력해주면 된다.

 

 

 

- num[0]=10에 대한 수열을 찾아보면 num[0]보다 이전 값은 없으므로 10자체 하나밖에 존재하지 않으므로 memo[0]=1이 됨

- 그 다음 num[1] = 20에 대한 수열을 찾아보면 num[0]=10으로 20보다 작기 때문에 {10,20} 이라는 부분수열이 되고, 길이는 2로 memo[1] = 2가 되는 것

 

memo[0] = {10} : 길이 1

memo[1] = {10,20} : 길이 2

memo[2] = {10} : 길이 1

memo[3] = {10,20,30} : 길이 3

memo[4] = {10,20} : 길이 2

memo[5] = {10,20,30,50} : 길이 4

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int num[];
    static int memo[];
    
       
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        num = new int[n];
        memo = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
        {
            
            num[i] = Integer.parseInt(st.nextToken());
        }
        
        
        for(int i=0; i<n; i++)
        {
        	memo[i] =1; //1로 초기화 
        	
        	//0~i이전 원소들 탐색
        	for(int j=0; j<i; j++)
        	{
        		//j번째 원소가 i번째 원소보다 작으면서 i번째 memo가 j번째 memo+1 값보다 작은 경우 
        		if(num[j]<num[i] && memo[i]<memo[j]+1)
        		{
        			memo[i] = memo[j]+1; //j번째 원소의 +1 값이 i번째 memo가 된다. 
        		}
        	}
        	
        }
        
        //최댓값(최대 길이) 탐색
        int max = -1;
        for(int i=0; i<n; i++)
        {
        	max = memo[i]>max ? memo[i]:max;
        }
        
        bw.write(max+"");        
        bw.flush();
        bw.close();
        
    }
}