백준 11053 가장 긴 증가하는 부분수열 java 풀이

가장 긴 증가하는 부분 수열 성공분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

57780

21983

14594

36.763%

문제

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

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

입력

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

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

출력

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

 

 

나의 풀이

 

주여진 요소마다 가질 수 있는 최대 길이값이 있을거라 생각하고 접근을 시작. 주어진 배열과 같은 길이의 dp[] 배열을 만들어서 최대 길이값을 저장하기로 하고, 자기 자신보다 작으면서 증가하는 요소가 앞에 몇개나 있나 카운트해서 dp[]배열에 저장했다. DP의 특성이 자연스럽게 드러났는데 주어진 arr[] 배열에서 자기보다 앞에 있으면서 값이 작은 요소를 찾고, 해당 요소가 dp[] 배열에 저장중인 값에 1을 더해주는 식으로 처리했다. 단 현재 요소의 dp[]의 값보다 앞의 요소의 dp[]값이 작다면 넘어가고 크거나 같을 때만 1을 증가시켜 주는 조건을 만족할때만 실행했다. 

dp[] 배열의 모든 값이 저장되고 나서 가장 큰 값을 찾으면 가장 긴 증가하는 부분수열의 길이가 된다.

 

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int num = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int[] arr = new int[num];
        for(int i=0; i<num; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int[] dp = new int[num];
        dp[0] = 1;
        
        for(int i=1; i<num; i++) {
            dp[i] = 1;
            for(int j=0; j<i; j++) {
                if(arr[j] < arr[i] && dp[i]<=dp[j]) {
                    dp[i] = dp[j]+1;
                }
            }
        }
        
        int max = 0;
        for(int i=0; i<num; i++) {
            max = Math.max(max, dp[i]);
        }
        
        bw.write(max+"\n");
        bw.flush();
    }
}