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

문제

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

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

---

풀이

11053번과 11722번 문제에서 사용했던 LIS(Longest Increasing Subsequence)와 LDS(Longest Decreasing Subsequence)를 동시에 사용해서 수열 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} 은 바이토닉 수열이 아닙니다.

---

코드

자바

탑다운 방식을 이용한 코드입니다.

dp1 배열은 각 인덱스가 맨 오른쪽인 부분 수열이 조건에 맞춰 가질 수 있는 가장 긴 부분 수열의 길이를 의미합니다.

LIS 함수에서 dp1[idx]가 0이라면 1로 초기화한 뒤에 i를 포함한 for문에서 arr[idx]와 arr[idx보다 왼쪽에 있는 인덱스(i)]를 비교합니다. 만약 arr[i]가 arr[idx]보다 작다면 LIS 함수를 재귀적으로 실행하며 dp1[idx] 값을 최신화한 후에 for문이 끝나면 그 값을 반환합니다.

dp2 배열은 각 인덱스가 맨 왼쪽인 부분 수열이 조건에 맞춰 가질 수 있는 가장 긴 부분 수열의 길이를 의미합니다.

LDS 함수에서 dp2[idx]가 0이라면 1로 초기화한 뒤에 i를 포함한 for문에서 arr[idx]와 arr[idx보다 오른쪽에 있는 인덱스(i)]를 비교합니다. 만약 arr[i]가 arr[idx]보다 작다면 LDS 함수를 재귀적으로 실행하며 dp2[idx] 값을 최신화한 후에 for문이 끝나면 그 값을 반환합니다.

모든 입력이 끝나면 i를 포함한 for문에서 LIS(i)와 LDS(i)를 1부터 n까지 실행하며 두 값을 더했을 때의 최댓값 max를 구한 뒤에 1을 빼고 출력합니다. dp1[x] + dp2[x]가 max일 때 arr[x]가 2번씩 체크됐기 때문입니다.

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

public class Main {

    static int[] arr, dp1, dp2;

    public static int LIS(int idx) {
        if (dp1[idx] == 0) {
            dp1[idx] = 1;
            for (int i = idx - 1; i > 0; i--) {
                if (arr[i] < arr[idx]) {
                    dp1[idx] = Math.max(dp1[idx], LIS(i) + 1);
                }
            }
        }
        return dp1[idx];
    }

    public static int LDS(int idx) {
        if (dp2[idx] == 0) {
            dp2[idx] = 1;
            for (int i = idx + 1; i < dp2.length; i++) {
                if (arr[i] < arr[idx]) {
                    dp2[idx] = Math.max(dp2[idx], LDS(i) + 1);
                }
            }
        }
        return dp2[idx];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];
        dp1 = new int[n + 1];
        dp2 = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int max = 0;
        for (int i = 1; i <= n; i++) {
            max = Math.max(max, LIS(i) + LDS(i));
        }
        System.out.println(max - 1);
    }
}

C언어

바텀업 방식을 이용한 코드입니다.

dp1 배열과 dp2 배열은 탑다운 방식의 코드에서의 의미와 동일하며 i를 포함한 for문으로 arr[i] 값을 입력받으며 dp1[i]와 dp2[i]는 1로 초기화합니다.

이후 i와 j를 포함한 이중 for문을 2번 실행하여 arr[i]값이 arr[i보다 오른쪽에 있는 인덱스(j)]보다 크고 dp1[i]보다 dp1[j] + 1이 크다면 그 값을, dp2[i]보다 dp2[j] + 1이 크다면 그 값을 넣어줍니다.

이후 i를 포함한 for문에서 dp1[i] + dp2[i] 값을 비교하며 두 값을 더했을 때의 최댓값 max를 구한 뒤에 1을 빼고 출력합니다. dp1[x] + dp2[x]가 max일 때 arr[x]가 2번씩 체크됐기 때문입니다.

#include <stdio.h>
#define math_max(a, b) a > b ? a : b
main() {
	int n;
	scanf("%d", &n);
	int* arr = (int*)malloc(sizeof(int) * n);
	int* dp1 = (int*)malloc(sizeof(int) * n);
	int* dp2 = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		dp1[i] = dp2[i] = 1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j] && dp1[i] < dp1[j] + 1) {
				dp1[i] = dp1[j] + 1;
			}
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		for (int j = n - 1; j > i; j--) {
			if (arr[i] > arr[j] && dp2[i] < dp2[j] + 1) {
				dp2[i] = dp2[j] + 1;
			}
		}
	}
	int max = 0;
	for (int i = 0; i < n; i++) {
		max = math_max(max, dp1[i] + dp2[i]);
	}
	printf("%d", max - 1);
}

---

결론

dp를 이용하여 LIS와 LDS를 이용하여 문제를 해결하였습니다. dp 배열을 2개 만들어야했고 dp1 배열과 dp2 배열이 갖는 의미가 서로 달랐습니다.

또한 바텀업 방식을 이용한 코드를 위와 같이 작성하게 되면 이중 for문을 2번 써야하므로 코드가 비효율적이고 지저분해 보이는 문제가 있었고 그래서 바텀업 방식과 탑다운 방식을 둘 다 사용하는 코드를 작성해봤습니다.

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

public class Main {

    static int[] arr, dp;

    public static int LDS(int idx) {
        if (dp[idx] == 0) {
            dp[idx] = 1;
            for (int i = idx + 1; i < dp.length; i++) {
                if (arr[i] < arr[idx]) {
                    dp[idx] = Math.max(dp[idx], LDS(i) + 1);
                }
            }
        }
        return dp[idx];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];
        dp = new int[n + 1];
        int[] dpLIS = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dpLIS[i] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (arr[i] > arr[j] && dpLIS[i] < dpLIS[j] + 1) {
                    dpLIS[i] = dpLIS[j] + 1;
                }
            }
            LDS(i);
        }
        int max = 0;
        for (int i = 1; i <= n; i++) {
            max = Math.max(max, dpLIS[i] + dp[i]);
        }
        System.out.println(max - 1);
    }
}