[BOJ 11053번] 가장 긴 증가하는 부분 수열(JAVA)

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

11053번: 가장 긴 증가하는 부분 수열

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String args[]) throws Exception {
		int iter=Integer.parseInt(br.readLine());
		int[] num=new int[iter];
		int[] cnt=new int[iter];
		String str[]=br.readLine().split(" ");
		for(int i=0;i<iter;i++) {
			num[i]=Integer.parseInt(str[i]);
		}
		for(int i=0;i<iter;i++) {
			cnt[i]=1;
			for(int j=0;j<i;j++) {
				if(num[i]>num[j]&&cnt[i]<=cnt[j]) cnt[i]=cnt[j]+1;
			}
		}
		int max=0;
		for(int i:cnt) {
			max=Math.max(max, i);
		}
		bw.write(max+"\n");
		bw.flush();
		bw.close();
	}
}

num 배열에는 수열을 순서대로 저장합니다.

cnt 배열에는 증가하는 부분수열의 길이를 저장합니다.

문제에서 예시로 든 10 20 10 30 20 50 을 예로 들어보겠습니다.

여기서 가장 긴 부분 수열은 10 20 30 50 으로 이루어진 길이가 4인 부분 수열입니다.

이 부분 수열은 10 20 30으로 이루어진 길이가 3인 부분 수열에 +1을 한 것이고, 10 20 30으로 이루어진 부분 수열은 10 20 으로 이루어진 길이가 2인 부분수열에 +1을 한 것입니다.

이 로직을 사용한 게 중간에 이중 for문으로 되어 있는 부분입니다.

현재 인덱스인 i의 num[i]보다 num[j]가 작고, 즉 수열의 숫자값이 더 작지만, j 번째 부분 수열의 길이가 i 번째 부분 수열의 길이보다 길 때 cnt[i]=cnt[j]+1로 해주어서 부분 수열을 연장해주었습니다.