[백준_11053번] 가장 긴 증가하는 부분 수열

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

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

[문제]

 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

[입력 조건]

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

[코드]

import java.util.*;

public class BaekJoon_11053 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
				
		int[] num=new int[n];
		int[] dp=new int[n];
				
		for(int i=0;i<n;i++)
			num[i]=sc.nextInt();
				
		for(int i=0;i<n;i++) {
			dp[i]=1; // 부분 수열은 자기 자신을 포함한 값이 최솟값이기 때문에 1로 초기화
					
			for(int j=0;j<i;j++) {
				/*
				* 자신 보다 값이 작지만 dp 값은 큰 경우 
				* j번째 원소의 dp 값에 i번째 수열을 포함한(+1) 값을 저장한다.
				*/   
				if(num[j]<num[i]&&dp[i]<dp[j]+1) {
					dp[i]=dp[j]+1;
				}
			}
		}
				
		// 최대 길이 탐색
		int max=-1;
		for(int i=0;i<n;i++) {
			max=dp[i]>max?dp[i]:max;
		}
		System.out.println(max);
	}
}

 

[고찰]

 부분 수열이란 주어진 수열에서 오름차순으로 구성 가능한 원소들을 선택하여 최대 길이를 찾아내는 것이다. 이번 문제는 재귀호출을 사용하여 푸는 방법 보다는 2중 for문을 사용하여 해결하는 것이 훨씬 쉬웠다. 부분 수열이 어떻게 만들어지는지만 이해하고 if 문의 조건만 잘 달아주면 어렵지 않게 해결할 수 있는 문제였다.