이것저것 개발 블로그

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

풀이)

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

public class Main_BJ_11053_가장긴증가하는부분수열 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        int[] dp = new int[n];
        for(int i=0; i<n; i++)
            dp[i] = 1;

        // 전체 보자
        for(int i=0; i<n; i++){
            // 이전부터 현재 위치까지
            for(int j=0; j<i; j++){
                //현재 위치보다 작은 애가 있으면
                if(arr[j] < arr[i])
                    //dp에 갱신하며 저장. 이때, 이전의 값보다 큰 값을 저장해야한다
                    dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }

        int ans = -1;
        for(int i=0; i<n; i++){
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);
    }//main
}

이 문제도 시리즈가 여러개 있는 것으로 안다.

하지만 오랜만에 풀어서 틀려버렸지요ㅋㅋㅋㅋㅋ

일단, 이건 완탐이 필요하다.

하지만, 중간부터 시작한 수열이 가장 길 수도 있고, 증가하는 수열이 연달아 나오지 않을 수 있기 때문에 주의해야한다.

따라서, dp[i] : i번째 수열을 포함한 가장 긴 수열

이때, dp배열은 기본 1이다.(가장 짧아도 수열 1개이기 때문!)

여기서 주의할 점은 dp 배열은 어떠한 위치에서 가장 긴 수열을 저장한 것이기 때문에,

꼭 dp 배열에서 가장 큰 값을 찾아야한다!