백준 11053번 JAVA

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

관찰

1. 완전탐색 - 첫번째 수부터 기준으로 증가 수열을 만들어서 최대의 길이를 찾는다!

• 시간이 n^2 걸린다! 1000*1000= 1000000 1초 안에 가능! 풀어보자!
• 반례 발생.. 10 30 20 21 40 일때 선형적인 탐색으로는 반례가 생긴다..

2. dp로 각각이 선택 될 때 안될때를 비교하면서 세어준다

• O(N*N)으로 가능할 듯! 풀어보자!

정답 코드

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

public class Main{
    static int n; // 배열의 길이
    static int[] arr; // 원본 배열
    static int[] dp; // 방문처리
    static int res; // 최대 거리
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 초기값 설정
        n = Integer.parseInt(br.readLine());
        arr = new int[n+1];
        dp = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < n+1; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        res = 0;

        //dp로 값 채워주기
        for(int i=1;i<n+1;i++) {
            // i부터 0까지 arr[i] 보다 작은 곳의 dp값 중에 최대값에 1을 더해서 만들기!
            int max = Integer.MIN_VALUE;
            for (int k = i - 1; k >= 0; k--) {
                if (arr[k] < arr[i]) {
                    if (max < dp[k]) {
                        max = dp[k];
                    }
                }
            }
            dp[i] = max + 1;
            // 입력된 dp 값 중 가장 큰 값이 정답!
            if(res < dp[i]) {
                res = dp[i];
            }
        }
        System.out.println(res);
    }
}

풀이

DP 배열에 각 칸을 올릴 수 있는 경우는
1. 배열의 인덱스가 더 작아야 하고
2. 원본 배열의 값이 더 작아야 한다
왜냐하면 증가하는 수열(순서존재) 이기 때문에!

그렇기에 각 칸에서 맨 앞까지 탐색해서 조건에 만족하는 최댓값+1로 dp 테이블을 채워간다!

느낀점

항상 완전탐색 풀이를 찾고 그 방법에서 더욱 좋은 방법을 찾아가는데 완전탐색 방법을 찾지 못해 당황스러웠다..
dp를 배우기 전에는 완전 손도 못 댈 문제이지 않았을까..