백준 11053번 (DP) - 가장 긴 증가하는 부분 수열 (JAVA) 문제 풀이

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

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

---

 

✏️ 문제

 

---

🔐 문제 해결

문제를 이해하지 못해서 헤맸던 문제이다..

아래 설명과 함께 풀이를 해보겠습니다.

 

1. 테이블 정의

1차원 배열 dp[i]는 i 번째 수까지의 가장 긴 증가하는 수열의 길이를 뜻합니다.

아직 잘 이해가 안되시는 분들을 위해 아래 코드로 설명해보겠습니다.

10 20 30 20 30

dp[0] = 1;    // 10
dp[1] = 2;    // 10 -> 20
dp[2] = 3;    // 10 -> 20 -> 30
dp[3] = 2;    // 10 -> 20
dp[4] = 3;    // 10 -> 20 -> 30

• dp[0]은 *제가 헷갈렸던 부분인데 시작 부분이기 때문에 길이 1을 가집니다. (dp[i]값은 1로 초기화를 해야합니다.)
• dp[1]은 0 번째 보다 증가하기 때문에 dp[0] + 1 값을 가집니다.
• dp[2]는 0 번째, 1 번째 순으로 증가하기 때문에 dp[1] + 1 값을 가집니다.
• dp[3]은 0 번째, 3 번째 순으로 증가하기 때문에 dp[0] + 1 값을 가집니다.
• dp[4]는 0 번째, 3 번째, 4 번째 순으로 증가하기 때문에 dp[3] + 1 값을 가집니다.

 

2. 점화식 세우기

위에서 설명했듯이 dp[i]는 j 번째 수 보다 큰 경우, dp[j] + 1 값을 가집니다. 하지만 우리는 최대값을 찾아야 하기 때문에 dp[i]와 dp[j] + 1 값 중 큰 값을 선택하면 됩니다.

 

식으로 나타내면 아래와 같습니다.

// 조건 : j 번째 수보다 i 번째 수가 클 경우
dp[i] = Math.max(dp[i], dp[j] + 1);

 

3. 초기값 설정

i 번째의 수들은 모두 수열의 시작점이 될 수 있기 때문에, dp[i]의 값은 모두 1로 초기화를 시켜야 합니다.

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

---

 

🗝 전체 코드

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

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

        int N = Integer.parseInt(bf.readLine());

        int[] arr = new int[N];
        int[] dp = new int[N];

        StringTokenizer st = new StringTokenizer(bf.readLine());

        // dp 원소를 1로 초기화!
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }

        // i번째를 기준으로 j번째의 수가 크다면 -> dp[i]+1값과 dp[j] 중 큰 값을 넣어줍니다.
        for(int i=0; i<N; i++) {
            for(int j=i+1; j<N; j++) {
                if(arr[i] < arr[j]) {
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                }
            }
        }

        // 결과 값으로 dp[i] 중 가장 큰 값을 출력해줍니다.
        int MAX = 0;
        for(int i=0; i<N; i++) {
            if(MAX < dp[i]) MAX = dp[i];
        }

        System.out.print(MAX);
    }
}