[백준 *Java] - 가장 긴 증가하는 부분 수열 (11053)

 

가장 긴 증가하는 부분 수열 문제보기

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

예를 들어,
수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 ?
{10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
{10, 20, 30, 50}
입력
첫째 줄에 수열 A의 크기 N(1 <= N <= 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 <= Ai <= 1,000)

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

 

문제를 보고 해석하자면?

가장 긴 증가하는 부분 수열이라는 이름되로,

주어진 A 수열에서 앞에서부터 갚을 하나씩 뽑아 증가하는 형태의 수열로 만드는 문제인 거 같아 그렇게 접근을 시도했습니다.

결과는 실패..

실패코드 입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int toCompareObject;
    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());
        toCompareObject = Integer.parseInt(st.nextToken());
        int cnt = 1;
        for (int i = 1; i < N; i++) {
            int A = Integer.parseInt(st.nextToken());
             if (toCompareObject < A) {
                 toCompareObject = A;
                 cnt++;
             }
        }
        System.out.println(cnt);
    }
}

실패 한 이유를 보니깐,

테스트 케이스 위주로 문제 풀이를 한 거 같습니다.

가장 긴 수열을 구하는 문제라, 첫째 자리부터 쭈욱 구하면 긴 수열이되는 줄 알았는데, 아니네요...

A1부터 시작해서 차례대로 가장 긴 수열의 길이를 확인해가면서

최종적으로 N번째 기준에서 가장 긴 수열을 찾는 문제입니다.

실패한 위의 코드에서 아래의 테스트케이스를 적용하면 출력값이 내가 처음 생각했던 거랑 다르게 나오는 것을 알 수 있습니다.

7 (입력값
5 10 3 30 5 7 20 (입력값)
3 (출력값)

 

자.. 다시 DP 문제 풀듯이 접근해서 문제를 풀어본다면,

차근차근 작은문제를 확인해가며 큰 문제를 풀어가야할 거 같습니다.

DP 테이블을 만들어, DP테이블 배열에는 해당 그 위치에 있는 인덱스 값에 맞게 가장 긴배열의 수를 넣는 방식으로 코드를 구현할 생각입니다.

아래 코드는 성공한 코드이며, 주석을 확인해주세요

 

첫 번째 방법

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

public class Boj_11053 {

    static int [] dp;
    public static void main(String args[]) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(bf.readLine());
    dp = new int[N];
    Arrays.fill(dp , 1); // 초기 세팅, 수열의 길이 default 는 1입니다.

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

    int[] target = new int[N];

    for(int i = 0; i < N; i++) {
        target[i] = Integer.parseInt(st.nextToken());
    } 
        
    for(int i = 0; i < N; i++) {
        for(int j = i+1; j < N; j++) {
            // 순차적으로 비교를해서 카운트 1씩 증가해주면, 각 수열의 길이를 알 수 있음.
            if(target[i] < target[j]) { 
                dp[j] = Math.max(dp[j], dp[i] + 1); // 수열 A1 부터 A2~ 전체 수열비교
                                                    // 수열 A2 부터 A3~ 전체 수열비교
                                                    // 수열 A3 부터 A4~ 전체 수열비교 ...
            }
        }
    }

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

    System.out.print(max); 
    } 
}

 

---

두 번째 방법

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

public class Boj_11053 {
    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 target[] = new int[N + 1]; // 입력 받은 수열의 길이 +1
        int DP[] = new int[N + 1];
        Arrays.fill(DP, 1); // 최소 배열은 길이가 1이니 전체 초기화

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

        int max = 1;
        for (int i = 2; i < DP.length; i++) {
            for (int j = 1; j < i; j++) { // 차례대로 idx i의 전 j들을 비교하여 길이를 + 시켜줍니다.
                if (target[i] > target[j] && DP[j]+1 > DP[i]) { // 값을 비교 해주고, 길이도 비교를 해줘야합니다. 현재 저장된 수열의 길이보다 작아야합니다.
                    DP[i] = DP[j] + 1;
                }
            }
            max = Math.max(max, DP[i]); //max 값을 갱신해줍니다
        }
        System.out.println(max);
    }
}