[백준] 동적계획법1 가장 긴 증가하는 부분수열 & 가장 긴 바이토닉 부분수열

비슷한 문제라서 같이 포스팅한다!

1. 가장 긴 증가하는 부분 수열

문제

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

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

풀이

dp[n]에 아직 방문하지 않은 경우(null일 때) dp[n]을 1로 초기화한다. (n위치에 있는 수가 항상 포함되므로 1로 초기화한다.) 후에 A[0~n-1]을 탐색하며 A[n]보다 작은 경우에 dp[n]값을 계산한다. 재귀호출한 값에 A[n]를 더 세는 것이기 때문에 +1을 해주고 dp[n]과 해당 값 중 더 큰 값을 dp[n]에 넣어준다.

코드

package 동적계획법1;

import java.util.Scanner;
public class No11053_가장긴증가하는부분수열 {

	static int[]A;
	static Integer[]dp;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		A=new int[N];
		dp=new Integer[N];
		
		for(int i=0;i<N;i++)
			A[i]=sc.nextInt();
		

		for(int i=0;i<N;i++)
			TotalLen(i);
		
		int max=dp[0];
		for(int i=1;i<N;i++)
			max=Math.max(max, dp[i]);
		
		System.out.println(max);
		
	}

	public static int TotalLen(int n) {
		if(dp[n]==null) {
			dp[n]=1;
			for(int i=0;i<=n-1;i++) {
				if(A[i]<A[n])
					dp[n]=Math.max(dp[n], TotalLen(i)+1);
			}
		}
		return dp[n];
	}
	
}

2. 가장 긴 바이토닉 부분 수열

문제

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

11054번: 가장 긴 바이토닉 부분 수열

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.
예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.
수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

풀이

위의 문제와 거의 유사하다. 기준값을 기준으로 양쪽으로 나누어서 각각 동적프로그래밍을 수행한 후 이 값을 더하여 계산한다.
예를 들어 기준값의 위치를 i라고 하면 위의 문제와 같은 방법으로 A[0~i-1]에 대하여 탐색하고 dp1[i]값을 계산한다. 또 기준값 이후로 감소하는 수열을 찾기 위해 A[i+1~N-1]에 대해 탐색하고 dp2[i]값을 계산한다.
결과는 두 값을 더해서 최댓값을 찾아주면 되는데 이 때 기준값이 두번 카운트되기 때문에 더한 값에 -1을 해주어야 정답이 된다.

코드

package 동적계획법1;

import java.util.Scanner;
public class No11054_가장긴바이토닉부분수열 {
	
	static int[] A;
	static Integer[] dp1;
	static Integer[] dp2;
	static int N;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		
		A=new int[N];
		dp1=new Integer[N];
		dp2=new Integer[N];
		
		for(int i=0;i<N;i++)
			A[i]=sc.nextInt();
		
		for(int i=0;i<N;i++) {
			MaxLen1(i);
			MaxLen2(i);
		}
		
		int max=-1;
		for(int i=0;i<N;i++)
			max=Math.max(dp1[i]+dp2[i], max);
		
		//기준값 원소를 중복해서 세는 경우를 방지하기 위해 -1
		System.out.println(max-1);
	}
	
	public static int MaxLen1(int n) {
		if(dp1[n]==null) {
			dp1[n]=1;
			for(int i=0;i<n;i++) {
				if(A[i]<A[n])
					dp1[n]=Math.max(dp1[n], MaxLen1(i)+1);
			}
		}
		
		return dp1[n];
	}
	
	public static int MaxLen2(int n) {
		if(dp2[n]==null) {
			dp2[n]=1;
			for(int i=n+1;i<N;i++) {
				if(A[i]<A[n])
					dp2[n]=Math.max(dp2[n], MaxLen2(i)+1);
			}
		}
		
		return dp2[n];
	}
}