[SWEA 3307번] 최장 증가 부분 수열

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWBOKg-a6l0DFAWr&categoryId=AWBOKg-a6l0DFAWr&categoryType=CODE&problemTitle=%EC%88%98%EC%97%B4&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

SW Expert Academy

 

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

public class Solution {
    static int N;

    static int[] num;
    static int result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        for (int test = 1; test <= T; test++) {
            N = Integer.parseInt(br.readLine());
            num = new int[N];
            st =new StringTokenizer(br.readLine());
            for(int i=0; i<N; i++){
                num[i] = Integer.parseInt(st.nextToken());
            }
            result=1;
            solution();
            System.out.println("#"+test+" "+result);


        }
    }

    private static void solution() {
        int [] dp =new int[N];
        dp[0]=1;


        for(int i=1; i<N; i++){
            dp[i]=1;

            for(int j=0; j<i; j++){
                if(num[j] < num[i] && dp[i] <=dp[j]){
                    dp[i] =dp[j] +1;
                }
            }

            result = Math.max(result, dp[i]);
        }
    }


}

 

와 문제 이해가 너무 안갔던 문제였다... 

DP를 활용해서 조건식을 구하면서 푸는 간단한 문제이다!!  LIS 문제! 

아래는 LCS 문제 참고!

https://balhae.tistory.com/255

[백준 9251번] LCS