[백준][Java]11053번 : 가장 긴 증가하는 부분 수열

[문제 링크]

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

---

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50} 이고, 길이는 4이다.

 

입력

• 첫째 줄에 수열 A의 크기
• 둘째 줄에 수열 A를 이루고 있는 원소들

출력

• 가장 긴 증가하는 부분 수열의 길이

입출력 예시

입력예시	출력예시
6 10 20 10 30 20 50	4

 

 

 

 

문제 풀이

• 다이나믹 프로그래밍으로 풀이
• dp[i] : array[i]를 마지막 값으로 가지는 증가 부분 수열들 중에서 가장 긴 부분수열의 길이
• array[i]가 어떠한 증가 부분 수열의 마지막 값이 되려면, array[i] 바로 이전에 오는 원소의 값이 array[i]보다 작아야 한다.
• 따라서 array[0]~array[i-1] 범위의 인덱스를 j라고 한다면,
  • array[i]와 비교해서 array[i] > array[j]를 만족하는 j중에서
  • dp[j]가 가장 큰 값에 1을 더한다.
• 이렇게 완성 dp 테이블에서 가장 큰 값이 가장 긴 증가 부분 수열의 길이가 된다.
• 위 과정을 하나씩 풀어서 아래와 같이 나타내보면 이해하기 더 쉽다.

• 점화식으로 나타내면 아래와 같다.

0 <= j < i 에 대하여,
dp[i] = max(dp[i], dp[j]+1) if array[i] > array[j]

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

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[] array = new int[n + 1];   //수열을 저장하는 배열
        int[] dp = new int[n + 1];  //가장 긴 증가하는 부분수열의 길이를 저장하는 dp테이블

        //수열 입력받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;  //dp 테이블 초기화
        }

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

        int result = 0;
        for (int i : dp) {
            result = Math.max(i, result);
        }
        System.out.println(result);
    }
}

 

 

나의 풀이(실패한 풀이)

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[] array = new int[n + 1]; 
        int[] dp = new int[n + 1];  

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            if (array[i - 1] < array[i]) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = dp[i - 1];
            }
        }
        
        System.out.println(dp[n-1]);
    }
}

 

여기에서 dp[i]는 array[0]~array[i]까지 원소들 중 가장 긴 증가 부분 수열의 길이를 의미한다.

(위의 풀이처럼 array[i]를 반드시 마지막 값으로 가지는 증가 부분 수열이 아니다.)

• dp[0]은 array[0] 하나이므로 dp[0] = 1
• dp[1]부터는 array[i]와 이전 원소인 array[i-1]를 비교해서
  • array[i-1] < array[i]을 만족하면, dp[i-1]에 1을 더한다.
  • 만족하지 않으면 dp[i-1]값을 그대로 가져온다.
• 이렇게 계산해서 dp[n-1]이 가장 긴 증가 부분 수열의 길이가 된다.

입출력 예시인 {10, 20, 10, 30, 20, 50}로 dp 테이블의 값을 계산해보면 dp = {1, 2, 2, 3, 3, 4} 로 정답은 4

 

위와 같이 생각했었지만 이 풀이에는 반례가 있다.

수열 array = {70, 30, 50, 60, 70, 1, 10}를 위의 풀이로 계산해보면 dp = {1, 1, 2, 3, 4, 4, 5} 이다.

하지만 실제로 가장 긴 증가 부분 수열은 {30, 50, 60, 70}으로 정답은 4 이다.

 

수열 array = {5, 10, 50, 60, 70, 20, 30, 40, 50}를 위의 풀이로 계산해보면 dp = {1, 2, 3, 4, 5, 5, 6, 7, 8} 이지만

실제로 가장 긴 증가 부분 수열은 {5, 10, 20, 30, 40, 50}으로 정답은 6 이다.

---

[참고]

https://thingjin.tistory.com/entry/백준-11053번-가장-긴-증가하는-부분-수열-파이썬

https://www.acmicpc.net/board/view/114371