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

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

11053번: 가장 긴 증가하는 부분 수열

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] arr = new int[n];
        int[] dp = new int[n]; // 증가 수열 길이를 저장할 배열
        dp[0] = 1; // 길이 1로 초기화
        int answer = dp[0];

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

        for(int i=1; i<n; i++){
            int max=0;
            for(int j=i-1; j>=0; j--){ // i값 이전의 값들 탐색
                if(arr[j]<arr[i] && dp[j] > max) max = dp[j]; // i값 보다 작고 max 값 보다 크다면 max 값 갱신
            }
            dp[i] = max+1; // 수열 길이 1증가
            answer = Math.max(answer, dp[i]); // 가장 긴 부분수열 찾기
        }
        System.out.println(answer);
    }
}

 

 

dp[i] = i번째 값을 마지막 항으로 하는 최대 증가 수열

 

 

입력받은 배열을 처음부터 탐색하면서, i값보다 작은 값들 중에 그 값을 마지막항으로 하는 수열 길이의 최댓값을 찾아 길이를 1증가 시켜 dp[i]를 저장한다.

dp[i]중에서 최댓값이 구하고자 하는 가장 긴 증가하는 부분 수열 길이이다. 

 

이 때, 처음엔 answer를 0으로 초기화해서 틀렸다. 

숫자 하나만 입력으로 들어왔을 때를 생각하면, answer는 길이 1이 되어야하기 때문에 1로 초기화 해줘야한다.