11722

가장 긴 감소하는 부분 수열

 

가장 긴 증가하는 부분 수열과 똑같음..

 

숏코드 중, d[2][N] 배열을 만들어 사용하는 것을 확인함.

저렇게 코딩하는 것에 익숙해지면 디버거를 사용할 때 좀 더 편하다.

d배열 참조 시 입력과 출력(arr+dp) 테이블의 값을 한눈에 확인 가능.

 

//내 코드
import java.util.Scanner;

class Main {

	static int N;
	static int answer;

	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int[] arr = new int[1001];
		int[] dp = new int[1001];

		for (int i = 0; i < N; ++i)
			arr[i] = in.nextInt();

		dp[0] = 1;
		answer = dp[0];

		for (int i = 1; i < N; ++i) {
			dp[i] = 1;
			for (int j = i - 1; j >= 0; --j) {
				if (arr[i] < arr[j] && dp[i] < dp[j] + 1)
					dp[i] = dp[j] + 1;
				
				answer = Math.max(dp[i], answer);
			}

		}
		/*
		for ( int i = 0; i < N ; ++i) {
			System.out.printf("[%d %d] ",i, dp[i]);
		}
		System.out.println();
		*/
		
		System.out.println(answer);
	}
}


ex)
6
10 30 10 20 20 10
[0 1] [1 1] [2 2] [3 2] [4 2] [5 3] 
3

//다른 사람 코드 https://www.acmicpc.net/source/13555211
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] d = new int[n][2];
		int max = 1;
		
		for(int i=0; i<n; i++) {
			d[i][0] = sc.nextInt();
			d[i][1] = 1;
			for(int j=0; j<i; j++) {
				if(d[j][0]>d[i][0]) {
					d[i][1] = Math.max(d[i][1], d[j][1]+1);
				}
				max = Math.max(max, d[i][1]);
			}
		}
		System.out.println(max);
	}

}