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

SWEA에서 최장 증가 부분 수열을 자바를 통해 풀어 보았다. 

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr&categoryId=AWBOKg-a6l0DFAWr&categoryType=CODE&problemTitle=3307&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

3307. 최장 증가 부분 수열.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

3307번 최장 증가 부분 수열

문제

주어진 두 수열의 최장 증가 부분 수열(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가 된다.

설명

DP문제 중 유명한 유형 중 하나인 최장 증가 부분 수열 LIS이다. 아래 코드에서는 2중 for문으로 O(n^2)에 풀었지만 이진 탐색을 활용하면 O(nlogn)에 풀 수도 있다.

 

배열 arr에는 LIS를 구할 수열이 저장되고 배열 dp는 인덱스 i까지의 LIS를 저장한다.

 

1. dp[i]는 기본적으로 자기 자신을 배열로 한 길이 1을 최솟값으로 저장된다.

2. 1부터 i 직전까지 인덱스 j에 대해서 만약 arr[j]가 arr[i]보다 작다면 arr[j] 뒤에 arr[i]를 연결하여 LIS를 유지할 수 있다. 3. dp[i]기 dp[j]+1보다 작다면 dp[i]를 dp[j]+1로 초기화시킨다. 

 

위 과정을 1부터 N까지 반복하면 dp[N]에는 배열 arr의 LIS가 저장된다. 

코드

//3307. 최장 증가 부분 수열.java
package webex;

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

public class 최장_증가_부분_수열_3307 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	
	 public static void main(String[] args) throws NumberFormatException, IOException {
		int T = Integer.parseInt(br.readLine());
		for(int t=1;t<=T;t++) {
			int N = Integer.parseInt(br.readLine());
			int[] arr = new int[N+1];
			int[] dp = new int[N+1];
			int answer=1;
			st = new StringTokenizer(br.readLine()," ");
			
			for(int i=1;i<=N;i++)arr[i] = Integer.parseInt(st.nextToken());
			
			for(int i=1;i<=N;i++) {
				dp[i]=1;
				for(int j=1;j<i;j++) {
					if(arr[j]<arr[i] && dp[i]<dp[j]+1) {
						dp[i] = dp[j]+1;
					}
				}
				if(dp[i]>answer)answer=dp[i];
			}
			sb.append("#"+t+" "+answer+"\n");
		}
		System.out.println(sb.toString());
	}
}