[백준] 11722 가장 긴 감소하는 부분 수열

www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

2020-11-22

---

import java.util.Scanner;

public class Main11722 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int arr[] = new int[N];
		int dp[] = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
			dp[i] = 1;
		}
		
		for(int i = 1; i < N; i++) {
			for(int j = 0; j <= i; j++) {
				if(arr[i] < arr[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}
		int answer = dp[0];
		for(int i = 1; i < N; i++) answer = Math.max(answer, dp[i]);
		System.out.println(answer);
	}
}

 

1. 초기 dp 배열의 값을 모두 1로 초기화 했다.

 

2. 비교할 기준 값을 배열 인덱스1부터 시작을 하며, 처음부터 현재 배열 인덱스까지 for문을 돌려서 비교를 했다.

 

3. 현재 수열의 값이 비교하는 수열 보다 작다면, 지금까지 저장해놓은 dp 값을 비교하여 비교하는 수열의 dp값+1을 해줘서 현재 수열의 dp 값을 업데이트 시켜줬다.

A[i]	10	30	10	20	20	10
dp[i]	1	1	2	2	2	3
현재 부분수열	{10}	{10}	{30, 10}	{30, 20}	{30, 20}	{30, 20, 10}

 

4. 마지막에 모든 값을 계산 한 후 제일 긴 수열의 값을 찾아야하므로, dp에서 가장 큰 값을 답으로 출력 했다.

 

---

처음에 단순하게 생각을 해서 풀어보니 전