[Java+Python]11054번, 가장 긴 바이토닉 부분 수열

문제

 

수열 $S$가 어떤 수 $S_{k}$를 기준으로 $S_{1} < S_{2} < ... S_{k-1} < S_{k} > S_{k+1} > ... S_{N-1} > S_{N}$을 만족한다면,

그 수열을 바이토닉 수열이라고 한다.

예를 들어, {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가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 수열 $A$의 크기 $N$이 주어지고, 둘째 줄에는 수열 $A$를 이루고 있는 $A_{i}$가 주어진다.

$(1 ≤ N ≤ 1,000, 1 ≤ A_{i} ≤ 1,000)$

 

출력

 

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

풀이

 

직전 문제였던 가장 긴 증가하는 부분수열(LIS)을 조금만 응용하면 되는 문제이다.

 

[Java+Python]11053번, 가장 긴 증가하는 부분 수열

[Java+Python]11053번, 가장 긴 증가하는 부분 수열

0번 인덱스부터 시작해서 정방향으로 LIS를 구해 결과를 저장할 배열을 하나 만들고,

 

N - 1번 인덱스에서 시작해 역방향으로 LIS를 구해 결과를 저장할 배열을 만든다.

 

이후 동적계획법으로 순회를 끝낸 뒤,

 

모든 인덱스에 대해서 가장 긴 길이의 바이토닉 부분 수열을 찾으면 되는 문제이다.

 

추가로 마지막 반복문에서 -1을 해주는 이유는 해당 바이토닉 수열의 최댓값이 두 번 겹쳐서 등장하기 때문이다.

 

먼저 자바 코드.

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

public class Prob11054 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		int[] increase = new int[n];
		int[] decrease = new int[n];
		int result = 1;

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.fill(increase, 1);
		Arrays.fill(decrease, 1);

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i]) {
					increase[i] = Math.max(increase[i], increase[j] + 1);
				}
			}
		}

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

		for (int i = 0; i < n; i++) {
			result = Math.max(result, increase[i] + decrease[i] - 1);
		}

		System.out.println(result);
	}
}

다음으로 파이썬 코드이다.

import sys

n = int(sys.stdin.readline().rstrip())
lst = list(map(int, sys.stdin.readline().rstrip().split()))
increase = [1 for _ in range(n)]
decrease = [1 for _ in range(n)]
result = 1

for i in range(n):
    for j in range(i):
        if lst[j] < lst[i]:
            increase[i] = max(increase[i], increase[j] + 1)

for i in range(n - 1, -1, -1):
    for j in range(n - 1, i, -1):
        if lst[j] < lst[i]:
            decrease[i] = max(decrease[i], decrease[j] + 1)

for i in range(n):
    result = max(result, increase[i] + decrease[i] - 1)

print(result)