백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열

문제 정보

---

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

 

 

핵심

---

DP 배열의 정의를 어떻게 내리느냐가 중요했다고 생각한다

매번 DP 관련 문제를 풀면서 느끼는 것이지만, 코드는 비슷한데 생각을 만들어 내느냐가 가장 중요한 것 같다

 

이 문제같은 경우에는 dp 배열을 다음과 같이 정의하였다

dp[i] : i번째 수를 선택했을 때, 가질 수 있는 최대의 길이

 

현재 위치를 무조건 택한다는 가정이 있기때문에,

1. 이전 dp 배열을 보면서 해당하는 값(배열 A)이 현재 위치의 값보다 작은지를 비교한다

2. 작다면, 작은 위치들 중에서 dp 배열의 값(해당 위치를 선택했을 때, 가질 수 있는 최대 길이) 중에서 가장 큰 값을 택함

3. 택했다면 해당 위치의 값 + 1(현재 위치를 택하기에) 이 dp[현재 위치] 가 된다

 

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] a = 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(a[j] < a[i])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

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

Arrays.fill() 을 통하여 dp 배열의 모든 위치의 값들을 1로 채워준 이유는, dp 배열은 전에 말했듯 현재 위치를 무조건 택한다는 가정이 존재하기 때문에 미리 더해준 것이다

 

Source Code on GitHub

---

 

(현재 백준허브가 작동을 안해서, 나중에 최신화 하겠습니다!)