https://www.acmicpc.net/problem/11054
11054번: 가장 긴 바이토닉 부분 수열
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
www.acmicpc.net
문제
수열 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)
출력
첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.
예제 입력 1
10
1 5 2 1 4 3 4 5 2 1
예제 출력 1
7
[문제 풀이]
Dynamic Programming을 이용하여 해결하는 문제이다.
점화식을 어떻게 구현해야 할 지 모르겠어서 다른 사람의 풀이를 결국 참고했다.
오름차순 수열, 내림차순 수열 두가지를 dp를 이용해서 풀어야한다.
오름차순 수열은 현재 인덱스에 해당하는 수가 부분 수열의 마지막 수라고 할 때, 오름차순 수열을 구현할 수 있는 부분 수열 길이의 최댓값을 저장할 것이고,
내림차순 수열은 현재 인덱스에 해당하는 수가 부분 수열의 가장 처음에 등장하는 수라고 할 때, 내림차순 수열을 구현할 수 있는 부분 수열 길이의 최댓값을 저장할 것이다.
예를 들어, 입력이 다음과 같다고 하자.
N = 10
A = {1, 5, 2, 1, 4, 3, 4, 5, 2, 1}
1. 오름차순, a_dp 배열
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
아직 한번도 탐색한 적 없다면(값이 0이면) 1로 초기화한다.(자기 자신으로만 부분 수열을 구현하는 경우)
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
현재 인덱스 값이 부분 수열의 마지막 수라고 할 때, 현재 인덱스보다 작은 인덱스에 해당하는 배열 값을 가지고 부분 수열을 만들 수 있는 부분 수열 길이의 최댓값을 저장할 것이다.
[a_dp]
기준값 - A[0]
길이가 최대인 부분 수열 - {1}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
기준값 - A[1]
길이가 최대인 부분 수열 - {1, 5}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
기준값 - A[2]
길이가 최대인 부분 수열 - {1, 2}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 1 | 2 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
기준값 - A[3]
길이가 최대인 부분 수열 - {1}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 1 | 2 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
기준값 - A[4]
길이가 최대인 부분 수열 - {1, 2, 4}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 1 | 2 | 2 | 1 | 3 | 0 | 0 | 0 | 0 | 0 |
기준값 - A[5]
길이가 최대인 부분 수열 - {1, 2, 3}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 1 | 2 | 2 | 1 | 3 | 3 | 0 | 0 | 0 | 0 |
기준값 - A[6]
길이가 최대인 부분 수열 - {1, 2, 3, 4}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 1 | 2 | 2 | 1 | 3 | 3 | 4 | 0 | 0 | 0 |
기준값 - A[7]
길이가 최대인 부분 수열 - {1, 2, 3, 4, 5}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 1 | 2 | 2 | 1 | 3 | 3 | 4 | 5 | 0 | 0 |
기준값 - A[8]
길이가 최대인 부분 수열 - {1, 2}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 1 | 2 | 2 | 1 | 3 | 3 | 4 | 5 | 2 | 0 |
기준값 - A[9]
길이가 최대인 부분 수열 - {1}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 1 | 2 | 2 | 1 | 3 | 3 | 4 | 5 | 2 | 1 |
오름차순 부분 수열은 다음과 같이 구성된다.
내림차순은 오름차순에서 했던 것과 반대로 가장 끝 인덱스부터 탐색하면 된다.
[d_dp]
기준값 - A[9]
길이가 최대인 부분 수열 - {1}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
기준값 - A[8]
길이가 최대인 부분 수열 - {2, 1}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 1 |
기준값 - A[7]
길이가 최대인 부분 수열 - {5, 2, 1}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 2 | 1 |
기준값 - A[6]
길이가 최대인 부분 수열 - {4, 2, 1}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 2 | 1 |
기준값 - A[5]
길이가 최대인 부분 수열 - {3, 2, 1}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 1 |
기준값 - A[4]
길이가 최대인 부분 수열 - {4, 3, 2, 1}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 0 | 0 | 0 | 0 | 4 | 3 | 3 | 3 | 2 | 1 |
기준값 - A[3]
길이가 최대인 부분 수열 - {1}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 0 | 0 | 0 | 1 | 4 | 3 | 3 | 3 | 2 | 1 |
기준값 - A[2]
길이가 최대인 부분 수열 - {2, 1}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 0 | 0 | 2 | 1 | 4 | 3 | 3 | 3 | 2 | 1 |
기준값 - A[1]
길이가 최대인 부분 수열 - {5, 4, 3, 2, 1}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 0 | 5 | 2 | 1 | 4 | 3 | 3 | 3 | 2 | 1 |
기준값 - A[0]
길이가 최대인 부분 수열 - {1}
| 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
| 1 | 5 | 2 | 1 | 4 | 3 | 3 | 3 | 2 | 1 |
내림차순 부분 수열은 다음과 같이 구성된다.
a_dp와 d_dp를 모두 구하고 나면 두 배열의 값을 합친다.
answer[i] = a_dp[i] + d_dp[i] - 1; 로 answer 배열을 완성한다.
-1을 해주는 것은 두 배열을 단순히 더하는 것이므로 기준 값(A[i])이 중복되기 때문이다.
a_dp
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 2 | 2 | 1 | 3 | 3 | 4 | 5 | 2 | 1 |
d_dp
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 5 | 2 | 1 | 4 | 3 | 3 | 3 | 2 | 1 |
answer
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 6 | 3 | 1 | 6 | 5 | 6 | 7 | 3 | 1 |
answer배열의 값 중 최댓값을 찾아 반환하면 된다.
[코드]
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] A = new int[N];
for(int i=0;i<N;i++)
A[i] = sc.nextInt();
int[] a_dp = new int[N];
int[] d_dp = new int[N];
//오름차순
for(int i=0;i<N;i++) {
if(a_dp[i]==0)
a_dp[i]=1;
for(int j=i-1;j>=0;j--) {
if(A[i]>A[j])
a_dp[i] = Math.max(a_dp[i], a_dp[j]+1);
}
}
//내림차순
for(int i=N-1;i>=0;i--) {
if(d_dp[i]==0)
d_dp[i]=1;
for(int j=i+1;j<N;j++) {
if(A[i]>A[j])
d_dp[i] = Math.max(d_dp[i], d_dp[j]+1);
}
}
int[] answer = new int[N];
int max = 0;
for(int i=0;i<N;i++) {
answer[i] = a_dp[i]+d_dp[i]-1;
if(max<answer[i])
max = answer[i];
}
System.out.println(max);
}
}'Algorithm > 백준' 카테고리의 다른 글
| [BOJ] 1021: 회전하는 큐(JAVA) (0) | 2021.11.04 |
|---|---|
| [BOJ] 10866: 덱(JAVA) (0) | 2021.11.03 |
| [BOJ] 1697: 숨바꼭질(JAVA) (0) | 2021.11.02 |
| [BOJ] 2293: 동전 1(JAVA) (0) | 2021.11.01 |
| [BOJ] 11049: 행렬 곱셈 순서(JAVA) (0) | 2021.10.29 |