[백준] S2 11722번 가장 긴 감소하는 부분 수열 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

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

[문제] 

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

[입력]

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

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

[출력]

첫째 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다.

 

---

[풀이]

1. 입력을 받아 map 배열을 채워준다.

2. 결과를 출력하기 위한 result 변수를 선언해준다.

3. 시작은 무조건 1이므로 dp배열을 1로 채워준다.

4. 현재 값 이전까지 값들을 비교해서 더 큰 값을 찾아준다.

5. 더 큰 값이 나오면 해당 번째의 dp 배열의 값 + 1과 현재 dp 배열의 값을 비교하여 더 큰 것으로 갱신해준다.

6. result에 최대값을 갱신해준다.

7. 모든 배열을 탐색하고 나면 결과를 출력해준다.

[접근]

1. 형재 값을 기준으로 이전에 나온 값들을 비교해 현재 값보다 크다면 해당하는 값의 dp 배열의 값 + 1과 현재 dp 배열의 값을 비교해 더 큰 값으로 갱신해주는 방식을 사용하면 되겠다고 생각하였다.

[코드]

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(reader.readLine());
		
		// 입력 배열
		int[] map = new int[n + 1];
		// dp 배열
		int[] dp = new int[n + 1];
		
		// 입력 값 채워주기
		StringTokenizer st = new StringTokenizer(reader.readLine());
		for (int i = 1; i <= n; i++) {
			map[i] = Integer.parseInt(st.nextToken());
		}
		
		int result = 0;
		for (int i = 1; i <= n; i++) {
			// 시작은 1
			dp[i] = 1;
			for (int j = 1; j < i; j++) {
				// 시작값과 이전값들을 비교
				// 이전 값이 크다면
				if (map[j] > map[i]) {
					// dp[j]는 이전까지 감소하는 부분 수열의 길이
					// 현재 길이와 이전까지 연결된 최대길이 + 1과 비교해서 최대값을 갱신
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			// 최대 길이 구하기
			result = Math.max(result, dp[i]);
		}
		
		System.out.println(result);
	}
}