[DP][Java][BOJ] #11053. 가장 긴 증가하는 부분 수열

#DP  #Silver2

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

 

🌷 문제 설명

✏️ 백준 연습문제: #11053. 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

⌨️ 입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

🖨️ 출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

입출력 예

입력	출력
6 10 20 10 30 20 50	4
7 5 1 6 2 7 3 8	4

 

💡 해결 포인트

1.  가장 처음에 오는 수가 가장 작은 수가 아닐 수도 있다는 점!

2. dp[i]는 수열의 i번째 숫자를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 
- 이전 숫자들 중 자기보다 작은 숫자를 찾아, 가장 긴 길이에 +1

3. 풀이 순서(5 1 6 2 7 3 8의 경우)
(1) dp[]를 1로 초기화 시키자(가장 긴 증가하는 부분 수열 길이 중 가장 작은 값)
=> [1, 1, 1, 1, 1, 1, 1]

(2) dp[0]
→ arr[0] = 5
→ 앞에 숫자가 없으므로 dp[0] = 1

(3) dp[1]
→ arr[1] = 1
→ arr[0] = 5
→ 앞에 숫자가 나보다 크므로 dp[1] = 1

(4) dp[2]
→ arr[2] = 6
→ 앞에 숫자(arr[0] or arr[1]) 둘 다 더 작은 값임
→ arr[0] = 5 => dp[2] = dp[0] + 1 = 2
→ arr[1] = 1 => d[2] = dp[1] + 1 = 2
→ 둘 중 더 긴 값 선택해서 dp[2]에 할당

(5) dp[3]
→ arr[3] = 2
→ 앞에 숫자  arr[1]만 arr[3]보다 작음 (1 < 2)
→ dp[3] = dp[1] + 1 = 2

(6) dp[4]
→ arr[4] = 7
→ arr[0], arr[1], arr[2], arr[3] 전부 작음
→ dp = [1, 1, 2, 2, 1, 1, 1] 이므로 가장 긴 dp[2], dp[3]에 1을 더한 수를
→ dp[4] = 3

(7) dp[5]
→ arr[5] = 3
→ arr[2], arr[3]만 작음. dp[2], dp[3] 수는 동일하므로 여기에다 1을 더한수를
→ dp[5] = 3

(8) dp[6]
→ arr[6] = 8
→ arr[0], arr[1], arr[2], arr[3], arr[4], arr[5] 전부 작음
→ 지금까지 갱신된 dp = [1, 1, 2, 2, 3, 3, 1] 이므로 가장 긴 dp[5]에 1을 더한 값을 
→ dp[6] = 4

 

🌷 내 코드

1. DP

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

public class BOJ_11053 {
  public static void main(String[] args) throws IOException {
    System.setIn(new FileInputStream("example.txt"));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine()); // 수열의 크기
    int[] arr = new int[N]; // 수열
    int[] dp = new int[N]; // 가장 긴 증가하는 부분 수열

    String[] line = br.readLine().split(" ");
    for (int i = 0; i < N; i++) {
      arr[i] = Integer.parseInt(line[i]);
    }

    for (int i = 0; i < N; i++) {
      dp[i] = 1; // 초기값 1
      for (int j = 0; j < i; j++) {
        if (arr[j] < arr[i] && dp[i] < dp[j] + 1) { // 나보다 작은 수가 있으면
          dp[i] = dp[j] + 1; // 수열 증가시키기
        }
      }
    }

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

    System.out.println(max);

  }
}

 

 

🌷 코멘트

처음에 최댓값 갱신 방신으로 생각했다가 틀렸다! 그치 이렇게 쉬울거면 실버2일리가 없지...ㅠ 
A={5, 1, 6, 2, 7, 3, 8} 인 경우를 생각해보기!
DP라는 거.. 내가 생각 해 낼 수 있는 범위의 내용인 걸까?

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!
~대가리 꽃밭인 디지털 노마드가 꿈이예요~
🧚‍♀️ Gyumin Lee
📧 gyumin.q.lee@gmail.com