백준 11053 - 가장 긴 증가하는 부분 수열 JAV

문제, 입출력, 테스트케이스

답을 눈 앞에 두고 뻉 돌아다닌 자의 최후.jpg

쉬운 것 같아서 점화식 짜고 대충 구현해서 풀다가 3시간 만에 풀었던 DP문제다. 매 순간 긴장을 놓치면 안 된다는 것! 자만하면 안 된다는 것을 다시 한번 일깨워준 문제...! 시간 복잡도 계산 정확하게 안 하고 점화식은 몇 분만에 구하고 시간 복잡도 터질까봐 배제했던 코드가 답이었다!.. ㅜㅜ

2차원 배열 선언하고 Comparator 재정의해서 정렬하고... 별짓을 다했다

<문제 접근/풀이 과정>
1. 1<= 수열 A의 크기 <= 1,000, 1 <= 수열을 이루는 수의 크기 <= 1,000  => int배열로 선언 가능
2. 완전탐색(부분집합) => 시간 복잡도 2^n = 최대 2^1,000 => 불가
3. n번에서 파악할 수 있는 최장 길이의 수열을 찾는 것은 그냥 문제와 동의어이므로 특정 논리가 필요
4. n번 째 수를 포함하면서 만들 수 있는 최장 수열 = max(n보다 작은 숫자로 이루어진 수열들 중 최장 수열)+1
5. n번째에서 파악할 수 있는 최장 길이의 수열 = max(n번 때까지 만든 최장 수열 중)
6. 4번을 점화식으로 구성 (dp배열 : n번 째 수를 포함하여 만든 최장 수열의 길이, arr배열 : n번째 수)
dp[n] = from i = 1 to n-1
              if(arr[i] < arr[n])
                  max = max(dp[i])
              dp[n] = max + 1
7. 결국 6번에서 구한 dp[n]들 중에서 가장 큰 수가 답이 된다.
8. 일반적으로 int로 선언된 배열을 초기화하지 않으면 0이 되니 바로 점화식에 맞게 값을 할당하는 경우가 있다.
하지만 해당 경우는 각각의 수들이 자기 자신을 포함한 수열을 만들 수 있기 때문에 dp 배열을 1로 초기화하고 시작하여야 한다.(중요!)
9. 이렇게 되면 시간 복잡도는 i=1일 때는 0번 탐색, i= 2일 때 1번 탐색, i=3일 때는 2번 탐색,..., i=n일 때는 n-1번 탐색 이므로  O(n*(n-1)/2) = O(n^2)의 시간 복잡도를 가진다 해당 문제의 입력 케이스를 고려하였을 때 많아봐야 499,500번 탐색이 걸린다는 뜻이다.

 

해당 소스코드는 상향식(바텀업) 방식으로 작성하였다.

package boj;

import java.util.Scanner;

public class Boj_11053 {
	static int arr[], n, answer;

	public static void main(String[] args) {
		// 1 <= 수열 A의 크기 <= 1,000, 1 <= A <= 1,000 -> int 선언 가능
		// n번째까지의 부분 수열 {이전까지의 최대 수,수열 길이} = {n번째 수 > n-1번째까지의 최대 수 ? n : n-1번째까지의 최대수,
		// n번째 수 > n-1번째까지의 최대 수 ? 이전까지 수열길이+1 : 이전까지의 수열 길이}
		// 입력 받을 수 최대 1001개 이므로 scanner나 bufferedreader&stringtokenizer 둘중 하나 쓰면 됨
		Scanner sc = new Scanner(System.in);
		// 2차원 배열에 정렬을 A의 크기 기준으로 오름차순 정렬한 후 인덱스 넘버 기준으로 dp배열 만들기

		int n = sc.nextInt();
		int arr[] = new int[n + 1];// 패딩사용(점화식 이 A(n) = A(n-1) 개념이므로. n=1일떄 n=0 필요
		int dp[] = new int[n + 1]; // 패딩사용(점화식 이 A(n) = A(n-1) 개념이므로. n=1일떄 n=0 필요
		int answer = 1;
		for (int i = 1; i <= n; i++) {
			arr[i] = sc.nextInt();
			dp[i] = 1;// 모두 자기자신만으로 수열 구성할 경우 1에 해당함.
		}

		for (int i = 1; i <= n; i++) {
			for (int j = i-1; j > 0 ; j--) {
				//i 보다 작은 곳 돌면서 i보다 arr[j]값이 arr[i]보다 작고 dp[j]값이 dp[i]값 보다 크거나 같으면 max과 비교하여 갱신
				if(arr[j] < arr[i] && dp[j] >= dp[i]) { 
					dp[i] = Math.max(dp[i], dp[j])+1;
				}
			}
//			System.out.println(i + "번째의 최장 길이" + dp[i]);
			answer = Math.max(dp[i], answer);
		}
		System.out.println(answer);

	}

	// 조건이 가장 '긴' '증가하는' '수열'
	// 1. 부분집합 = 2^n승 => 불가
	// 2. 뒤에서부터 보면 가장 긴 감소하는 '수열'찾기 문제로 변모
	// 3. n번째 수까지에서 최장 길이 수열은 = n-1번째 수까지의 최장 길이 수열 or (n-1번째 수까지의 최장 길이 수열 + 1)
	// 4. 최장 길이 수열은 어떻게 구할까? -> n번쨰 까지의 최장 길이 수열 = n번째 수 > n-1 일 경우 n번째 수를 넣은 수열 or
	// 10 20 10 30 20 50
	// O O X O X O
	// 8 6 9 1 4 6 7 4 3 7 4 7 2 5 2 10 1
	// 1 1 2 1 2 3 4 2 2 4 3 4 2 4 2 5 1
	// 8
	// O
	// 8 6
	// O X
	// X O
	// 8 6 9
	// X O O
	// 8 6 9 1
	// X O O X
	// 8 6 9 1 4
	// X O O X X
	// 8 6 9 1 4
	// O X O X X
	// 8 6 9 1 4
	// X X X O O
	// 8 6 9 1 4
	// O X O X X
	// 8 6 9 1 4 6
	// X X X O O O

}