[백준 11053번] 가장 긴 증가하는 수열 - DP

백준 11053번 동적 계획법(Dynamic Programming)으로 풀 수 있는 문제이다.

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

문제는,

수열 A에서 이를 어떻게하면 가장 긴 부분 수열로 나열할 수 있고, 이의 길이를 출력으로 보여주는 문제이다.

처음 문제의 풀이 과정을 생각할 때, 너무 단순하게 생각했다.

왜 이 문제를 DP을 이용해서 풀어야하는지 몰라서 소팅을 실행하고 중복된 숫자만 제거해서 최종적으로 남은 숫자의 개수를 출력했다.

 

이렇게 문제를 풀었을 때, 테스트 케이스는 통과했다.

하지만 실패했는데 문제를 잘못이해했던 것 같다.

 

바로, 처음부터 순서대로 입력받은 수열에서 차례로 나열할 때 이를 증가하는 수열로 어떻게 작성하는지 묻는 문제였다.

 

'틀렸습니다'를 받고 문제를 잘못이해하고 있는 것 같아서 질문을 통해 문제를 이해하였다.

 

문제를 풀기 위해 차례로 탐색하면서 이전의 수열에서 현재 수보다 큰 것이 몇가지 있는지 세어서 별도로 저장하는 것이 핵심이었다.

즉, 별도로 저장하는 것을 DP로 이용하여 점화식을 세운다.

 

1️⃣ 30의 자리에 맞는 DP 값을 구할 때, 이전의 값을 탐색한다. (빨간색)

 

2️⃣ 여기서 30보다 작은 값을 찾고 DP 값을 확인해서 작은 값들을 찾고 그 중 Max 값을 찾는다.

 

3️⃣ 마지막으로 찾은 Max 값에 +1을 하여 DP에 저장한다.

 

여기서 핵심인 조건문은 30보다 작은 것을 찾기만하면 안된다.

DP 값을 꼭 비교해서 현재 DP보다 작거나 같은 경우에만 +1을 실행하여야한다.

 

전체 소스코드를 보면서 30일 경우에만 조건이 있고 없고를 돌려보면 왜 그런지 쉽게 알 수 있다.

 

전체 소스코드는

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

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

        String[] input = br.readLine().split(" ");
        int[] sequence = new int[N];

        for (int i = 0; i < N; i++)
            sequence[i] = Integer.parseInt(input[i]);

        int[] DP = new int[N];

        for (int i = 0; i < N; i++) {
            DP[i] = 1;
        }

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

        int max = 0;
        for (int i = 0; i < N; i++) {
            if (max < DP[i]) { max = DP[i]; }
        }

        System.out.println(max);
    }
}