[Java] BOJ 11722번 가장 긴 감소하는 부분 수열

11722번: 가장 긴 감소하는 부분 수열

---

풀이

LIS(최장 증가 수열)을 응용하여 해결했습니다.

LIS(최장 증가 수열)과는 반대로 현재 숫자(i)보다 앞의 숫자들이(j) 작을 경우 해당 숫자가 있는 memo[j] + 1이 현재 숫자가 있는 memo[i] 보다 크다면 값을 경신하게 했습니다.

---

코드

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

public class Main {
	public static int N, answer;
	public static int[] A = new int[1001];
	public static int[] memo = new int[1001];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i = 1; i <= N; ++i) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = 1; i <= N; ++i) {
			memo[i] = 1;
			
			for (int j = 1; j < i; ++j) {
				if (A[i] < A[j] && memo[i] < memo[j] + 1) {
					memo[i] = memo[j] + 1;
				}
			}
		}
		
		for (int i = 1; i <= N; ++i) {
			answer = (answer < memo[i]) ? memo[i] : answer;
		}
		
		System.out.println(answer);
	}
}

---

pyo7410/Algorithm