SW Expert Academy - 3307번(최장 증가 부분 수열)

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr

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

public class Solution {

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(reader.readLine());

        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(reader.readLine()); // 수열의 길이
            int[] num = new int[N];
            int[] DP = new int[N];

            int ans = 0;

            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            for (int i = 0; i < N; i++) {
                num[i] = Integer.parseInt(tokenizer.nextToken());
                for (int j = 0; j < i; j++) {
                    if (num[i] > num[j]) DP[i] = Math.max(DP[i], DP[j]);
                }

                DP[i]++;
                ans = Math.max(ans, DP[i]);
            }

            sb.append("#").append(t + 1).append(" ");
            sb.append(ans).append("\n");
        }

        System.out.println(sb);
    }

}

• 기본 DP를 이용하여 풀 수 있는 간단한 문제였다.