[BOJ] 11722번 가장 긴 감소하는 부분 수열 - Java

백준 11722번 가장 긴 감소하는 부분 수열 바로가기
시간 제한 : 1초
메모리 제한 : 256MB
레벨 : Silver 2

문제 설명

문제

수열 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)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제

예제 입력 1
6
10 30 10 20 20 10

예제 출력 1
3

문제 풀이 - DP

public static void main(String[] args) throws IOException {
	BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

	int N = Integer.parseInt(read.readLine());

	int[] A = new int[N];
    StringTokenizer stoi = new StringTokenizer(read.readLine());
    for(int i = 0; i < N; i++) {
    	A[i] = Integer.parseInt(stoi.nextToken());
    }

	int[] DP = new int[N];
    Arrays.fill(DP, 1);

	int max = -1;
    for(int i = 0; i < N; i++) {
    	for(int j = 0; j < i; j++) {
        	if(A[j] > A[i]) {
            	DP[i] = Math.max(DP[i], DP[j] + 1);
            }
        }

		max = Math.max(max, DP[i]);
    }

	System.out.println(max);
}

풀이 과정은 간단하다. j < i까지 반복문을 쭉 돌면서, 나보다 큰 원소가 있다면 DP 값을 갱신한다. 각 원소의 DP를 차례대로 구하고, 가장 긴 구간을 구하기 위해 DP[i]의 최대값을 갱신해주는 과정을 반복하면 되는 것이다.

이때 주의할 점은 DP[i] = Math.max(DP[i], DP[j] + 1);로 구해야 한다는 것이다. 만약 현재 A[j] > A[i]라고 해서 DP[j] + 1로 값을 바로 확정해버리면, A[j]와의 상대적인 비교만 가능하고 더 긴 구간에 대한 고려를 할 수 없기 때문이다.

이 부분만 주의하면 간단하게 풀 수 있는 문제이다. 감소하는 부분 수열, 증가하는 부분 수열은 다 이런 식으로 풀면 된다. 하지만 나는 자꾸 까먹어서 (ㅜㅜ) 간단하게나마 정리를 해보았다!