[BAEKJOON] 11054 가장 긴 바이토닉 부분 수열

문제 요악

• 알고리즘 분류: 동적 계획법
• 난이도: Gold5
• 문제 요약
  • 수열 S가 있다. 수열 S[1] < S[k] > S[N - 1] 만족하는 최장 길이 수열을 구해라
    • 증가 했다가 중간에 감수하는 수열을 구해라
• 사이트 주소: https://www.acmicpc.net/problem/11054

2565번: 전깃줄

문제 풀이

 이번 문제는 동적계획법인데 그 중 LIS 최장 증가하는 수열을 구하는 문제이다. LIS 관한 설명은 아래의 사이트에서 확인 하면 된다.

https://jih3508.tistory.com/46

[알고리즘 이론] LIS(Longest Increasing Subsequence) 최장 증가 부분 수열

 문제 접근 방법

  이번 문제는 LIS 응용 문제이다. LIS를 두 번 구해서 합하면 되는 문제이기 때문에 접근 방법만 알면 된다. 

index = 0

index=1

index=2

index=3

위 그림을 보면 위 문제 예제를 표로 나타낸것이고  0번째 인덱스 부터 3번째 인덱스를 구해야 될 범위를 그림으로 표현 한것이다. 초록색은 증가하는 수열 노란색은 감소하는 수열을 나타낸것이라고 보면된다.  하지만 감소 하는 수열 영력을 구할라면 뒤에서 부터 구해야 되기 때문에 한번은 정면으로 한번은 뒤집어서 구한다음 뒤집은 dp 배열을 다시 거꾸로 해서 증가하는 수열 구하는 방식으로로 할것이다. 위 방법을 아래 와 같은 그림으로 표현 할 수가 있다.

순방향 일때 dp의 값

역방향 일때 dp의 값

 위 이미지를 역방향 했을때를 구한 다음 다시 원래 방향 대로 구한값이다.

 

각 2가지 방법을 구했으면 더하면 되지만 -1 한 다음 더해야 한다. 그 이유는 각 인덱스 위치에서 자기 자신이 포함이 되어 있기 때문에 그냥 2번을 더하면 자기 자신을 두번 반영이 된다.

두 개의 경우를 구하고 더하면 아래와 같은 표로 나타 낼 수가 있다.

 

그 다음 가장 큰 값을 구하면 된다. 이 중에서 가장 큰 값은 7이다. 

 

이번 문제는 구하는 방법만 알면 코드로 구현하는 것은 어렵지 않기 때문에 접근 방법만 알면 된다.

Code

Python

# LIS 함수
def LIS(S, N, num):
    dp = [num] * N
    for i in range(N):
        for j in range(i):
            if S[i] > S[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return dp

N = int(input())
S =  list(map(int, input().split()))

dp_l = LIS(S, N, 1)
S.reverse()
dp_r = LIS(S, N, 0)
dp = []
dp_r.reverse() # 뒤 집어서 구했기 때문에 인덱스를 맞추기 위해서 다시 뒤집어야 한다.
for i in range(N):
    dp.append(dp_l[i] + dp_r[i])

print(max(dp))

Java

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

public class NUMBER11054 {

	public static void main(String[] args) throws  IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] S = new int[N]; 
		int[] reverseS = new int[N]; // 역순으로 저장할 배열
		
		for(int i = 0; i < N; i++) {
			S[i] = Integer.parseInt(st.nextToken());
			reverseS[N-i-1] = S[i]; // 역순으로 저장
		}
		
		int[] dp_r = LIS(S, N, 1);
		int[] dp_l = LIS(reverseS, N, 0);
		int[] dp = new int[N];
		for(int i = 0; i < N; i++) {
        	// index 맞춰야 되서 정방향 역방향으로 순서대로 더한다.
			dp[i] = dp_r[i] + dp_l[N - i -1]; 
		}
		
		System.out.println(Arrays.stream(dp).max().getAsInt());
	}
	
	
	// LIS 구하는 함수 
	public static int[] LIS(int[] S, int N, int num) {
		int[] dp = new int[N];
		Arrays.setAll(dp, i -> num);
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < i; j++) {
				if(S[i] > S[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}
		
		return dp;
	}
}