[백준 *Java] - 가장 긴 감소하는 부분 수열 (11722)

 

가장 긴 감소하는 부분 수열 문제보기

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)

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

 

가장 긴 증가하는 부분 수열이는 문제와 비슷한 거 같습니다.

그래서 바로 설계 없이 문제를 풀 생각입니다.

간략하게 정리하자면, 

이중 포문을 이용하여, target 인덱스의 값과 인덱스 앞부터 비교를하면서 부분 수열의 길이를 DP에 저장할 생각입니다.

주의 할점은 길이체크를 꼭 조건 걸어주어야 합니다.

로직 짜다가 DP[j] <= DP[i] 로 조건을 주었는데, 이것도 실상 테스트케이스에 통과가 되지만, 잘못된 로직입니다.

아래는 성공한 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int [] DP;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int A = Integer.parseInt(br.readLine());

        DP = new int[A+1];
        Arrays.fill(DP, 1);
        int [] target = new int[A+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < A; i++) {
            target[i] = Integer.parseInt(st.nextToken());
            //System.out.println(target[i]);
        }

        for (int i = 1; i < A; i++) {
            for (int j = 0; j < i; j++) {
                if (target[j] > target[i] && DP[j] >= DP[i]) {
                    DP[i] = DP[j] + 1;
                }
            }
        }

        int max = 0;
        for (int n : DP) {
           if (n > max) max = n;
        }
        System.out.println(max);

    }
}