백준 11568번(Java)

문제는 다음과 같다.

예제는 다음과 같다.

입력
5
8 9 1 2 10

출력
3

자세한 것은 직접 가서 보자.

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

간단한 DP문제다. 그래서 DP연습하기 좋다.

문제의 목적은 다음과 같다.
가장 긴 순 증가를 찾아라

우리는 다음과 같이 생각할 수 있다.
1. 두 번째 DP의 요소부터 N번째 요소까지 조회한다.
2. 조회하는 과정 내에서 현재 DP의 요소의 이전단계들의 값을 비교하고 현재 요소가 더 크면 DP의 현재의 값를 증가시킨다.
3. 값을 증가시킬때 DP의 기존의 값이 더 크다면 변경없이 넘어간다.
4. 조회가 모두 끝나면 DP내에서 가장 큰 값이 정답이다.

코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Main {
    static int[] arr;
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
        dp = new int[n];

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

        dp[0] = 1;
        for(int i = 1; i < n; i++){
            dp[i] = 1;
            for(int j = 0;  j < i; j++){
                if(arr[j] < arr[i])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

        int ans = Arrays.stream(dp)
                        .max()
                        .getAsInt();

        System.out.println(ans);
    }
}

끝!