[백준] DP - 11722번, 가장 긴 감소하는 부분 수열

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

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

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

출) 첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

---

풀이

1. 테이블 정의 : n만큼의 길이의 수열을 입력받고 각각을 비교하여 부분 수열의 길이를 출력

2. 점화식 : dp[i] = dp[j] + 1;

3. 초기값 : dp[i] = 1;

 

지난 풀이와 비슷하다. 현재 값과 이전 값들을 하나하나 비교하면서 감소 수열을 찾는 것이다.

다만 신경써야하는 건 감소 순열이기 때문에 다음의 조건을 만족해야 한다.

• 이전 값들이 현재 값보다 커야 한다(arr[j] > arr[i]).
• 현재 누적 값(dp[i] = 1)보다 이전 누적값+1이 더 커야한다.
• 동일 값일 경우 누적값은 같다.

왜 누적값에 대한 조건을 넣어야하는가?

(반례) 4 / 6 5 7 3 (정답) 3 (출력) 2

테스트케이스	6	5	7	3
출력	1	2	1	2
정답	1	2	1	3

 

 

코드

Scanner + System.out.println();

import java.util.Scanner;
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] dp = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }
        for(int i=0; i<arr.length; i++) {
            dp[i] = 1;
            for(int j=0; j<i; j++) {
                if(arr[j]>arr[i] && dp[i] < dp[j]+1) {
                    dp[i] = dp[j] + 1;
                } else if (arr[i] == arr[j]) {
                    dp[i] = dp[j];
                }
            }
        }
        int max = 0;
        for(int i=0; i<dp.length; i++) {
            max = dp[i]>max?dp[i]:max;
        }
        sc.close();
        System.out.println(max);
    }
}

 

BufferedReader + System.out.println();

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

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<n; i++) {
            if(st.hasMoreTokens()) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i=0; i<arr.length; i++) {
            dp[i] = 1;
            for(int j=0; j<i; j++) {
                if(arr[j]>arr[i] && dp[i] < dp[j]+1) {
                    dp[i] = dp[j] + 1;
                } else if (arr[i] == arr[j]) {
                    dp[i] = dp[j];
                }
            }
        }
        int max = 0;
        for(int i=0; i<dp.length; i++) {
            max = dp[i]>max?dp[i]:max;
        }
        br.close();
        System.out.println(max);
    }
}

 

---

 

코드 길이는 주석을 추가하면서 좀 차이가 나게 됐다.

최적화를 위해서는 Scanner보다 BufferedReader를 사용하는 편이 훨씬 좋겠다.