[백준/Java] 11053 - [Silver II] 가장 긴 증가하는 부분 수열

 

문제 링크

문제 설명

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

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 A_i가 주어진다. (1 ≤ A_i ≤ 1,000)

출력

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

 

---

처음엔 백트래킹 문제인줄 알았는데 시간 초과가 나서 제한사항을 살펴보니 dp 문제였다 . . .

시체

 

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

public class Main {
    static int answer = 0;
    static int N;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        dfs(0,0,0);
        System.out.println(answer);
        br.close();
    }

    static void dfs(int depth, int size, int lastNum){
        if(depth == N){
            answer = Math.max(answer, size);
            return;
        }

        if(lastNum < arr[depth]){
            dfs(depth+1, size+1, arr[depth]);
        }
        dfs(depth+1, size, lastNum);
    }
}

버리기 아까워서 올리는 백트래킹 코드

 

그래서 dp로 다시 풀었답니다

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());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N+1];
        int[] dp = new int[N+1];

        for(int i=1; i<=N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.fill(dp,1); // dp 초기 값을 1로 채워주기
        // 가장 짧은 증가하는 부분 수열의 길이는 1이므로

        int answer = 1;

        for(int i=2; i<=N; i++){
            for (int j = 1; j < i; j++) {
                if(arr[i] > arr[j] && dp[i] <= dp[j]){
                // 현재 값이 이전 값보다 크고
                // 현재 증가하는 부분 수열의 길이가
                // 이전 값의 길이보다 작거나 같을 때
                // 길이 + 1
                    dp[i] = dp[j] + 1;
                }
            }
            answer = Math.max(answer, dp[i]);
        }
		
        System.out.println(answer);
        br.close();
    }
}