[알고리즘] 백준 11054 자바 JAVA 동적프로그래밍 LIS 최장 증가 수열

 

 

 

이 문제는 11053문제 바로 뒤에 나오는 문제이다. 다만 가장 큰 값을 중심으로 왼쪽과 오른쪽으로 값이 작아지는 그 부분 수열의 길이를 알아야하는 문제이다.

 

처음에 접근 방식은 먼저 가장 긴 증가 부분 수열 방식으로 값을 셋팅해놓고, 큰 값과 그의 인덱스를 저장한 뒤, 그 인덱스부터 가장 긴 감소 부분 수열 방식으로 다시 검색하는 방식으로 진행했었는데, 될 법 한데 자꾸 예외에 부딪히고 코드가 읽기 힘들어졌다. 어찌어찌하면 될 것 같은데 동적프로그래밍의 특성을 제대로 활용하고 싶다고 가정한다면 좋은 접근 법은 아니다. 

 

그렇다면 좋은 접근 법은 무엇이냐?

1. 가장 긴 증가하는 부분 수열을 통해 먼저 카운팅한다.

2. 가장 긴 감소하는 부분 수열을 통해 카운팅을 한다.

3. 합치고 -1한다.

 

 

 

코드를 보자

 

public class BaekJoon_16_11054 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(reader.readLine());

		int[] A = new int[1001];
		int[][] dp = new int[2][1001]; // 0 : 가장 긴 증가하는 부분 수열, 1: 가장 긴 감소하는 부분 수열

		StringTokenizer st = new StringTokenizer(reader.readLine());
		for (int i = 1; i <= n; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}

		dp[0][1] = 1; // 왼쪽 시작
		for (int i = 2; i <= n; i++) {
			dp[0][i] = 1;
			for (int j = 1; j < i; j++) {
				if (A[i] > A[j])
					dp[0][i] = Math.max(dp[0][i], dp[0][j] + 1);
			}
		}

		dp[1][n] = 1; // 오른쪽 시작
		for (int i = n - 1; i > 0; i--) {
			dp[1][i] = 1;
			for (int j = n; j > i; j--) {
				if (A[i] > A[j]) // 시작점이 다를 뿐이라 작은걸 고르는게 아니고 왼쪽에서 시작하는것과 마찬가지로 큰것을 골라서 체크해주면 된다.
					dp[1][i] = Math.max(dp[1][i], dp[1][j] + 1);
			}
		}

		// 두 카운트한 값을 더해서 첫번째에 넣어준다.
		for (int i = 1; i <= n; i++) {
			dp[0][i] += dp[1][i];
		}

		int max = Integer.MIN_VALUE;
		for (int i = 1; i <= n; i++) {
			if (max < dp[0][i])
				max = dp[0][i];
		}

		writer.write(max - 1 + "");

		writer.flush();
		reader.close();
		writer.close();
	}

}

 

어쩌다 보니 코드가 제법 길어졌다. 사실 완전 압축시킬 수도 있는데 그렇게 했더니 코드가 뭔가 한번에 분석하기가 힘들어서 그냥 차례대로 작성했다. 

 

단순하게 DP의 특성을 이용해서 푸는 가장 이상적인 방법이다. 왼쪽 시작과 오른쪽 시작을 모두 카운팅해주고, 두개를 더해버리면 우리가 원하는 가장 큰 값을 구할 수 있다.

 

여기서 포인트는 왼쪽 시작에서 시작을 1로 잡았고, 오른쪽 시작도 시작을 1로 잡았기 때문에 두 DP카운트 값을 더할 때, 1값이 중복으로 더해진다는 문제가 존재한다. 이는 출력시에 -1로 빼주었다.