[백준]11053-가장 긴 증가하는 부분 수열 문제 풀이(Java,자바)

https://www.acmicpc.net/problem/11053

 

들어가며

이 문제는 단순히 보면 백트래킹으로 풀기 십상이다.

나도 그렇게 풀어서 처음에 깔끔하게 틀렸다.

 

그렇다.

이 문제는 dp다..

 

코드

package solved.ac.class4;

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

public class 백준11053_가장긴증가하는부분수열 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] nums = 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 (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int result = Arrays.stream(dp).max().getAsInt();
        System.out.println(result);
    }
}

풀이

dp[i]

- nums[i]로 끝나는 가장 긴 증가하는 부분 수열의 길이

- 초기값은 1로 설정, 최소 nums[i]는 가지고 있기 때문에 길이는 1이다.

 

i라는 배열 인덱스가 있다고 가정하자.

그러면 0 ~ i-1 까지의 배열 엔덱스 중 제일 큰 값을 가져와 1을 더하면 dp[i]가 된다.

 

10 20 10 30 20 50

예를 들어 i가 3이라고 가정하자.

nums[i] = 30이다.

dp[i]는 30로 끝나는 가장 긴 증가하는 부분 수열의 길이를 나타낸다.

그러면 dp[i]는 i =0, i =1, i =2 를 끝으로 가지는 증가하는 부분 수열의 길이 중에서 제일 큰 값에다가 1을 더하면 된다.

1을 더한다는 뜻은 30을 그 수열에 추가하면 끝이기 때문이다.

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

그렇기에 nums[j] < nums[i]를 만족할 때 실행한다.

증가하는 부분 수열을 찾기 위함이다.

 

int result = Arrays.stream(dp).max().getAsInt();
System.out.println(result);

이렇게 반복하다보면 dp[] 배열 어딘가엔 최대값이 들어가게 된다.

그 중 최대값을 찾으면 끝이다.