[백준,BOJ 11053] 가장 긴 증가하는 부분 수열(JAVA 구현,추가풀이)

 

-내 생각

  우선 이 문제는 LIS알고리즘이라고 하여서 무언가 알고리즘에 대한 기본적인 개념 같은 것이 있을 줄 알고 검색해봤는데, 그렇지 않고 그냥 알고리즘 문제들 중 대표적인 문제의 유형 중 하나인 것 같다. 그래서 의도치 않게 문제 해설을 봐버리게 되어서 분석해보았는데, 크게 어려운 부분은 없었다. 그러나 여기서 사용한 2중 for문의 경우는 수열의 길이가 10 이상이 돼버리면 1초에 완료할 수가 없다고 한다. 왜냐하면 2중 for문은 O(N^2)의 시간 복잡도를 가지기 때문이라고 한다. LIS를 푸는 O(NlogN) 방법이 있다고 하는데, 여기엔 이진 탐색을 사용한다고 하니 후에 글로 남겨야겠다.

 

-해법

  우선 가장 긴 증가하는 부분 수열이라는 문제에서 핵심은 일정한 숫자들이 주어질 때 첫 번째 숫자부터 점점 커지는 숫자들을 선택할 때 가질 수 있는 최대의 개수를 의미한다. 예제의 경우에서 3번째 10을 선택하고 30 ,50 순으로 선택하면 총 3개밖에 선택하지 않았으므로 정답이 되지 않는다.

 

  2중 for문을 사용하는 이유는 주어진 데이터에서 하나의 기준을 잡은 후 처음부터 해당 기준까지 탐색을 해야 하기 때문인데 이 부분은 코드를 보면 확실히 이해가 될 것이다.

 

import java.util.*;

public class Main {
	static int n;
	
	static int dp[], cost[];
	
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		n=sc.nextInt();
		dp = new int[n+1];
		cost = new int[n+1];
		
		dp[1] =1; // 초기 시작지점은 1로 초기화
        
		for(int i =1;i<=n;i++) { // 데이터 입력
			cost[i] = sc.nextInt();
		}
		
		for(int i=2;i<=n;i++) { // 1이 초기화 되어 있으므로 2번 째 숫자부터 기준을 잡고 시작
			dp[i] =1; // 1로 저장해둔 이유는 아래의 조건에 걸리지 않으면 그 값을 유지하기 위해서이다.
			for(int j=1;j<i;j++) { // 2번을 기준으로 할 때 첫 번째 숫자부터 2번 까지 탐색... 반복
				if(cost[i]>cost[j]) { // 기준 이전의 숫자들을 탐색해 값이 기준값 보다 작으면,
					dp[i] = Math.max(dp[j]+1,dp[i]); // 기존의 저장 값과 작은 값이 가지는 값+1 중 큰 값을 저장
				}
			}
		}
		int max = Integer.MIN_VALUE;
		
		for(int j=1;j<=n;j++) { // 최종 dp배열 중 가장 큰 값이 가장 긴 수열이 된다.
			if(dp[j]>max) {
				max = dp[j];
			}
		}
		System.out.println(max);
	}
	
}

---

  추가풀이라기 보다는 코드를 좀 더 간소화시켰다.

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int a[] = new int[n];
		int dp[] = new int[n];
		
		
		for(int i=0;i<n;i++) {
			a[i] = in.nextInt();
		}
		
		
		for(int i=0;i<n;i++) {
			dp[i] = 1;
			
			for(int j=0;j<i;j++) {
				// 기준값보다 작은 값이 존재하며, 현재 저장된 수열의 길이가 작은 값의 수열 길이+1 보다 작으면,
				if(a[j]<a[i] && dp[i]<dp[j]+1) {
					dp[i] = dp[j]+1;
				}
			}
		}
		
		// 정렬 후
		Arrays.sort(dp);
		
		// 마지막 인덱스 값 출력
		System.out.println(dp[n-1]);
		
		in.close();
	}

}