[백준] 11054: 가장 긴 바이토닉 부분 수열 (DP) - JAVA

단계별 문제풀이 23단계 (동적계획법1)

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

 

 

# 예제

입력 :  첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

10
1 5 2 1 4 3 4 5 2 1

 

 

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

7

 

# 필요개념

바이토닉 수열은 중심 (S) 을 기준으로 멀어질수록 수가 작아지는 수열을 의미한다. 앞뒤를 한번에 보기 힘들기 때문에, 함수를 나누어 계산하기로 했다.

 

up 과 down 함수를 만들었다. 함수의 역할은 다음과 같다.

• up() -> 반환: up[ ]
  
  • up[ ] 에다가 오름차순이 되게 하는 원소의 개수를 넣는다.
  • up[3]를 보고 있다면, up[2], up[1] 순으로 돌면서 input[3] > input[2]를 만족시키면 up[3] 에 기존 값과 up[2] + 1 중 더 큰 값을 갱신한다.
• down() -> 반환: down[ ]
  
  • down[ ] 에다가 내림차순이 되게 하는 원소의 개수를 넣는다.
  • up [ ] 과 반대로 동작한다고 보면 된다.

 

up[ ] 과 down[ ] 에는 자기자신을 포함해 각각 오름차순과 내림차순을 이루는 원소의 개수가 들어있게 된다. 따라서 up[i] + down[i] 가 가장 큰 수를 구하고, 그 수에서 1을 빼면 답이 나온다. 

 

1을 빼는 이유는 자기 자신이 두 번 들어가있기 때문!

 

# Code

import java.io.*;
import java.util.*;
import static java.lang.Math.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] inputs = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 1 ; i <= N ; i++) {
            inputs[i] = Integer.parseInt(st.nextToken());
        }

        int[] upDp = up(inputs);
        int[] downDp = down(inputs);
        int max = 0;
        for (int i = 1 ; i <= N ; i++) {
            max = Math.max(max, upDp[i] + downDp[i]);
        }
        System.out.println(max - 1);
    }

    private static int[] down(int[] inputs) {
        int[] downDp = new int[inputs.length];
        downDp[inputs.length - 1] = 1;
        for (int i = inputs.length - 2 ; i >= 1 ; i--) {
            for (int j = i + 1 ; j < inputs.length ; j++) {
                if (inputs[i] > inputs[j]) downDp[i] = max(downDp[j] + 1, downDp[i]);
            }
            downDp[i] = max(1, downDp[i]);
        }
        return downDp;
    }

    private static int[] up(int[] inputs) {
        int[] upDp = new int[inputs.length];
        for (int i = 1 ; i < inputs.length ; i++) {
            for (int j = i - 1 ; j >= 0 ; j--) {
                if (inputs[i] > inputs[j]) {
                    upDp[i] = max(upDp[j] + 1, upDp[i]);
                }
            }
        }

        return upDp;
    }
}

 

 

# 결과