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

이 문제는 다이나믹 프로그래밍을 이용하여 증가하는 부분 수열을 만드는 문제입니다.

저는 입력받은 값들을 저장하는 intArr 배열과 메모이제이션한 값들을 넣은 dp배열을 사용하였습니다.

추가적인 설명은 코드를 보면서 드리도록 하겠습니다.

---

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

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

        int N = Integer.parseInt(br.readLine());
        int[] intArr = new int[N];
        int[] dp = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++)
            intArr[i] = Integer.parseInt(st.nextToken());

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

            for(int j = 0; j<i; j++){
                if(intArr[i]>intArr[j] && dp[i] < dp[j]+1)
                    dp[i] = dp[j] + 1;
            }
        }

        int max = Integer.MIN_VALUE;
        for(int i = 0; i<N; i++)
            max = Math.max(max, dp[i]);

        System.out.println(max);
    }
}

저는 이 문제를 풀 때 기본적으로 dp[i]에 1을 넣은 다음 이전에 있던 값들과 비교하게 만들었습니다.

이전의 값들과 비교해나가면서 지금 들어온 값이 이전의 값보다 큰데 dp 배열의 값이 그보다 같거나 작다면 이전의 값의 dp에 1을 추가하였습니다.

이를 그림으로 보여드리도록하겠습니다.

제가 그림으로 표현하는 부분은 아래의 코드입니다.

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

    for(int j = 0; j<i; j++){
        if(intArr[i]>intArr[j] && dp[i] < dp[j]+1)
            dp[i] = dp[j] + 1;
    }
}

문제의 예제는 다음과 같은 그림으로 표현할 수 있습니다.

i가 0일 때 dp[i]에 우선 1을 넣고 그 안의 for 문은 j<1일 때만 반복하므로 실행하지 않습니다.

위의 그림은 아래의 조건식을 만족합니다. intArr의 값이 이전 값보다 크고 dp[i]의 값도 초기 값이 1이었기 때문입니다.

if(intArr[i]>intArr[j] && dp[i] < dp[j]+1)

그 다음 과정에서는 위의 조건식을 만족하지 못하기 때문에 초기값인 1이 그대로 들어갑니다.

그 다음으로는 j가 0부터 순회를 돌기 때문에 dp[3]번에는 우선 2가 들어갑니다.

그러나 j가 1이 되면 dp[1]이 2이고 intArr[1] = 20 이므로 intArr[3]의 값이 더 크고 dp[3] < dp[2]+1이 만족되어서
dp[3]에는 3의 값이 들어갑니다.

intArr[4]도 같은 과정을 반복해서 2가 대입됩니다.

마지막 i가 5가 되었을 때도 위의 과정을 반복하여 dp[3]보다 1추가된 값인 4가 들어오게 됩니다.

이런 식으로 dp 배열을 만든 뒤 마지막으로 dp수열을 순회하면서 가장 큰 값을 출력하면 됩니다.