[백준] 가장 긴 증가하는 부분 수열 JAVA

반응형

728x90

[백준] 가장 긴 증가하는 부분 수열 - SILVER II 11053번

---

접근

• dp

---

풀이

주어지는 숫자들 중 증가하는 가장 긴 수열의 개수를 찾아내는 문제이다. 처음 문제를 보고 한 생각은 따로 정렬된 배열을 두고 정렬된 숫자를 원본 배열에 매칭시키며 개수를 구하면 되는 게 아닌가 했는데 수열에 위치할 다음 숫자를 무조건 골라야 하는 게 아닌 스킵하고 넘어갈 수 있으므로 사용할 수 없는 방법이었다.

 

이 문제처럼 보통 바로 다음만 고려하는게 아닌 뒤의 경우도 고려해야 하는 조건인 경우 dp를 사용하면 해결할 수 있다. 동적 배열을 이용하여 각 단계별 가장 긴 경우의 길이를 구해 차근차근 쌓아가는 것이다. 앞의 최댓값들을 활용해 늘려나가는 bottom-up 방식이기 때문에 각 인덱스까지의 부분수열의 최대 길이를 구할 수 있다. 

	int N = Integer.parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

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

스트림을 사용해 입력 받는 값을 int 배열로 변환해 주었다. 그리고 dp로 사용할 배열을 선언하고 초기값으로 각 인덱스의 자기 자신만을 수열로 갖는 경우인 1을 채워주었다.

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

배열을 생성하는 과정이다. 인덱스를 늘려가며 해당 인덱스 까지의 최대 수열을 찾는 과정이다. 동작 과정은 아래를 참고한다.

arr = {10, 20, 10, 30, 20, 50}
dp = {1, 1, 1, 1, 1, 1}

i = 1 arr[1] = 20
arr[1] > arr[0] -> true
dp[1] = Math.max((dp[1] = 1), (dp[0] = 1) + 1 = 2) -> dp[1] = 2
dp = {1, 2, 1, 1, 1, 1}

i = 2 arr[2] = 10
arr[2] > arr[0] -> false
arr[2] > arr[1] -> false
dp[2] = 1 -> 변화X
dp = {1, 2, 1, 1, 1, 1}

i = 3 arr[3] = 30
arr[3] > arr[0] -> true
dp[3] = Math.max((dp[3] = 1), (dp[0] = 1) + 1 = 2) -> dp[3] = 2

arr[3] > arr[1] -> true
dp[3] = Math.max((dp[3] = 2), (dp[1] = 2) + 1 = 2) -> dp[3] = 3

arr[3] > arr[2] -> true
dp[3] = Math.max((dp[3] = 3), (dp[2] = 1) + 1 = 2) -> dp[3] = 3
dp = {1, 2, 1, 3, 1, 1}
.
.
.
최종 결과
dp = {1, 2, 1, 3, 2, 4}

각 인덱스 까지 만들 수 있는 최대 길이를 dp배열 인덱스에 저장해가며 다음 검사할 숫자가 앞의 수열에 이어 붙일 수 있다면 앞의 수열 최대 길이에 새로운 숫자 하나를 붙여 최댓값을 갱신하는 구조이다.

	int result = 0;
        for (int l : dp) {
            result = Math.max(result, l);
        }

완성된 수열을 순회하며 가장 긴 길이를 찾는다.

---

전체 코드

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

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[] arr = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

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

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

        int result = 0;
        for (int l : dp) {
            result = Math.max(result, l);
        }

        System.out.println(result);
        br.close();
    }
}