백준 11054 - 가장 긴 바이토닉 부분 수열 - JAVA

문제, 입출력, 테스트케이스

바로 직전에 풀었던 백준 11053 문제의 응용편이다. 11053 풀땐 3시간이 걸렸지만 바로 응용해서 푸니 10분? 20분만에 푼 것 같다. 어쩐지 정답률이 높더라...

2022.03.31 - [알고리즘공부(AlgorithmStudy)/문제풀이(ProblemSolving)] - 백준 11053 - 가장 긴 증가하는 부분 수열 JAV

백준 11053 - 가장 긴 증가하는 부분 수열 JAV

<문제 접근/풀이과정>
1. 1부터 n까지는 오름차순인 증가하는 최장 수열 길이 찾아서 dp[n][0]에 할당(최장 수열 길이는 위 링크 참조!)
2. n부터 1까지 내림차순으로 순회하면서 증가하는(n 내림차순 순회이므로) 최장 수열 길이 찾아서 dp[n][1]에 할당
3. 선택할 수 있는 부분은 dp 배열의 n번째의 첫 번 째 또는 두 번 째인덱스를 0으로 초기화할 지, 1로 초기화할 지이다. 왜냐하면 자기 자신 자체가 하나의 수열로 1의 길이를 갖기 때문에 해당 문제의 답인 max(dp[n][0] + dp[n][1])에서 자기자신을 포함한 수열을 dp[n][0]에 포함시키면 초기화를 1로 해줘야하고 그렇지 않으면 초기화 해주지 않아도 된다. 그냥 머리가 아프다면 초기화 자체를 하지 않고 마지막에 + 1을 해주는 방법도 있다!

여하튼 11053번을 푼다음 이 문제를 접한 것이라면 1차원 배열을 2차원으로 선언 하거나, 다른 배열 선언해서 각각 값을 넣어둬서 합한 값이 최대인 것이 답이다. 

 

해당 소스코드는 상향식(바텀업) 방식으로 DP를 구현하였다.

 

 

package boj;

import java.util.Scanner;

public class Boj_11054 {
	static int arr[], n, answer;

	public static void main(String[] args) {
		// 최장 수열을 두포인터 개념으로 구하면 되지 않을까?
		// 1 <= 수열 A의 크기 <= 1,000, 1 <= A <= 1,000 -> int 선언 가능
		// n번째 수 > n-1번째까지의 최대 수 ? 이전까지 수열길이+1 : 이전까지의 수열 길이}
		// 입력 받을 수 최대 1001개 이므로 scanner나 bufferedreader&stringtokenizer 둘중 하나 쓰면 됨
		Scanner sc = new Scanner(System.in);
		// 2차원 배열에 정렬을 A의 크기 기준으로 오름차순 정렬한 후 인덱스 넘버 기준으로 dp배열 만들기

		int n = sc.nextInt();
		int arr[] = new int[n + 1];// 패딩사용(점화식 이 A(n) = A(n-1) 개념이므로. n=1일떄 n=0 필요
		int dp[][] = new int[n + 1][2]; // 패딩사용(점화식 이 A(n) = A(n-1) 개념이므로. n=1일떄 n=0 필요
		int answer = 1;
		for (int i = 1; i <= n; i++) {
			arr[i] = sc.nextInt();
			dp[i][0] = 1;// 모두 자기자신만으로 수열 구성할 경우 1에 해당함.
			dp[i][1] = 0;// 모두 자기자신만으로 수열 구성할 경우는 증가하는 최장 수열에 넣어놨음 해당함.
		}
		// 증가하는 최장 수열 구하기
		for (int i = 1; i <= n; i++) {
			for (int j = i-1; j > 0 ; j--) {
				//i 보다 작은 곳 돌면서 i보다 arr[j]값이 arr[i]보다 작고 dp[j]값이 dp[i]값 보다 크거나 같으면 max과 비교하여 갱신
				if(arr[j] < arr[i] && dp[j][0] >= dp[i][0]) { 
					dp[i][0] = Math.max(dp[i][0], dp[j][0])+1;
				}
			}
		}
		
		// 감소하는 최장 수열 구하기
		for (int i = n; i >= 1; i--) {
			for (int j = i+1; j <= n ; j++) {
				//i 보다 큰 곳 돌면서 i보다 arr[j]값이 arr[i]보다 크고 dp[j]값이 dp[i]값 보다 크거나 같으면 max과 비교하여 갱신
				if(arr[i] > arr[j] && dp[i][1] <= dp[j][1]) { 
					dp[i][1] = Math.max(dp[i][1], dp[j][1])+1;
				}
			}
		}
		
		for (int i = 1; i <= n; i++) {
//			System.out.println(i +"번째에서 만들 수 있는 증가하는 최장 수열 :" + dp[i][0] +"&&" + i + "번째에서 만들 수 있는 감소하는 최장 수열 :" + dp[i][1]);
			answer = Math.max(answer, dp[i][0]+dp[i][1]);
		}
		System.out.println(answer);

	}
//	10
//	1 5 2 1 4 3 4 5 2 1
//	1 2 2 1 3 3 4 5 2 1
//	1 5 2 1 4 3 3 3 2 1
}