3307. 최장증가부분수열 (LIS)

SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

주어진 두 수열의 최장 증가 부분 수열(Longest Increasing Subsequence)의 길이를 계산하는 프로그램을 작성하시오.

수열 { A1, A2, ... , AN }의 최장 증가 부분 수열 B는 다음과 같이 정의된다.

{ B1, B2, ... , BK }에서 0≤K≤N, B1 ≤ B2 ≤ ... ≤ BK이고,

AB1 ≤ AB2 ≤ ... ≤ ABK인 최대 K로 구성된 수열이다.

예를 들어, 수열이 { 1, 3, 2, 5, 4, 7 } 이라면, 최장 부분 증가 수열의 길이는 4가 된다.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에는 수열의 길이 N(1≤N≤1,000)이 주어진다. 

둘째 줄에는 수열의 원소 N개가 공백을 사이에 두고 순서대로 주어진다.

각 수열의 원소는 1 이상 231-1 이하의 자연수이다.

[출력]

각 테스트 케이스마다 ‘#T’(T는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 증가 부분 수열의 길이를 출력한다.

package a0916;

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

public class 최장증가부분수열 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		int tc=0;
		BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("res/3307_input.txt")));
		tc = Integer.parseInt(br.readLine());
		StringTokenizer st;
		
		for(int i=0; i<tc; i++) {
			
			int n = Integer.parseInt(br.readLine());
			
			st = new StringTokenizer(br.readLine());
			int[] arr = new int[n];
			int[] dp = new int[n];
			int max =0;
			dp[0]=1; //첫번째 시작은 무조건 1
		
			for(int j=0; j<n; j++) {
				
				arr[j]= Integer.parseInt(st.nextToken());
				
			}
			int maxn =0;
			for(int j=1; j<n; j++) { //j 순회
				dp[j]=1;//시작은 1
				for(int k=0; k<j; k++) { //0~j 까지
					
					if(arr[j]>arr[k] && dp[j]<dp[k]+1) {//j번째 수가 더 크고 k번째 수에서 1을 더한것 보다 크다면
						
						dp[j]=dp[k]+1; //dp를 갱신해준다.
						
					}
					
					
					
				}
				
				maxn = Math.max(maxn, dp[j]); //최장 수열을 찾기 위해 max를 쓴다.
				
			}
			
		System.out.println("#"+(i+1)+" "+maxn);	
			
		
			
		}
		
		
		
		
		
	}
	
	
}