| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 63033 | 32660 | 25534 | 51.372% |
문제
수열 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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.
답안
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
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());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] numbers = new int[n];
for (int i = 0; i < n; i++) {
int number = Integer.parseInt(st.nextToken());
numbers[i] = number;
}
int[] upwardMemo = new int[n];
int[] downwardMemo = new int[n];
int result = 0;
for (int i = 0; i < n; i++) {
upwardMemo[i] = 1;
downwardMemo[i] = 1;
int peek = 0;
for (int j = 0; j < i; j++) {
if (numbers[j] < numbers[i]) {
upwardMemo[i] = Math.max(upwardMemo[i], upwardMemo[j] + 1);
}
else if (numbers[j] > numbers[i]) {
downwardMemo[i] = Math.max(downwardMemo[i], downwardMemo[j] + 1);
peek = Math.max(peek, upwardMemo[j]);
}
}
downwardMemo[i] = Math.max(downwardMemo[i], peek + 1);
result = Math.max(result, upwardMemo[i]);
result = Math.max(result, downwardMemo[i]);
}
System.out.println(result);
}
}
풀이
LIS, LDS 알고리즘을 사용하지 않고 의 시간복잡도를 가지는 DP로 문제를 풀었다.
입력의 최대 크기가 이므로, 이 정도의 입력 크기라면 의 알고리즘으로 시간적으로 가능할 것으로 생각했기 때문이다.
메인 아이디어는 각 수열의 숫자마다
- 부분수열의 숫자가 올라가고 있는 상태에 있다고 가정할 때,
- 부분수열의 숫자가 내려가고 있는 상태에 있다고 가정할 때
두 가지 경우의 바이토닉 수열의 최대 길이를 저장하는 것이다.
예를 들어, 121451이라는 수열의 바이토닉 수열을 찾는 예시를 생각해보자.
| 수열 | 1 | 2 | 1 | 4 | 5 | 1 |
|---|---|---|---|---|---|---|
| 올라가는 상태에서의 최대 길이 | ||||||
| 내려가는 상태에서의 최대 길이 |
수열의 맨 첫 번째 숫자인 1부터 생각해보자.
| 수열 | 1 | 2 | 1 | 4 | 5 | 1 |
|---|---|---|---|---|---|---|
| 올라가는 상태에서의 최대 길이 | 1 | |||||
| 내려가는 상태에서의 최대 길이 | 1 |
1이라는 부분수열만 놓고 생각해볼 때, 1이라는 숫자는 올라가는 상태에 있는 것일 수도, 내려가는 상태에 있는 것일 수도 있다. 두 경우 모두, 바이토닉 수열 1의 길이는 1이다.
수열의 두 번째 숫자인 2로 넘어가자.
| 수열 | 1 | 2 | 1 | 4 | 5 | 1 |
|---|---|---|---|---|---|---|
| 올라가는 상태에서의 최대 길이 | 1 | 2 | ||||
| 내려가는 상태에서의 최대 길이 | 1 | 1 |
2라는 숫자를 1,2와 같이 올라가는 상태에 있는 부분수열로 간주할 수 있는지 확인하기 위해, 수열의 첫 번째 숫자를 확인한다. 수열의 첫 번째 숫자인 1은 두 번째 숫자인 2보다 작으므로 올라가는 상태의 부분수열로 볼 수 있다.
반면 2라는 숫자를 내려가는 상태에 있는 것으로 본다면, 바이토닉 수열의 최대 길이는 1이 된다.
수열의 세 번째 숫자인 1로 넘어가자.
| 수열 | 1 | 2 | 1 | 4 | 5 | 1 |
|---|---|---|---|---|---|---|
| 올라가는 상태에서의 최대 길이 | 1 | 2 | 1 | |||
| 내려가는 상태에서의 최대 길이 | 1 | 1 | 3 |
올라가는 상태에서의 최대 길이를 구하기 위해 수열의 이전 숫자들을 확인하니, 모두 1보다 크거나 같은 숫자이다. 이때문에, 1이라는 숫자를 이전의 숫자들과 함께 부분수열로 묶음으로써 올라가는 상태에 있는 부분수열로 간주할 수 없다. 따라서 세 번째 숫자인 1에서부터 부분수열을 시작하는 것이 최선이므로, 최대 길이 1이 저장된다.
내려가는 상태의 경우, 수열에 이전에 등장한 모든 숫자들이 수열의 세 번째 숫자인 1보다 작거나 같으므로, 이전의 숫자들과 함께 부분수열로 묶음으로써 내려가는 상태에 있는 부분수열로 간주할 수 없다. 하지만, 바이토닉 수열은 올라가는 상태의 수열과 내려가는 상태의 수열의 합이므로, 올라가는 상태에서의 최대 길이를 가지는 수열을, 피크를 찍고 내려가는 상태의 수열로 방향을 바꿀 수 있다. 즉, 이 상태에서는 1,2,1과 같이 올라가던 수열의 방향을 바꿀 수 있고, 이때 최대 길이는 3이다.
수열의 네 번째 숫자인 4이다.
| 수열 | 1 | 2 | 1 | 4 | 5 | 1 |
|---|---|---|---|---|---|---|
| 올라가는 상태에서의 최대 길이 | 1 | 2 | 1 | 3 | ||
| 내려가는 상태에서의 최대 길이 | 1 | 1 | 3 | 1 |
올라가는 상태에서의 최대 길이를 구하기 위해 수열의 이전 숫자들을 확인하니, 1, 2, 1 모두 4보다 작으므로 이전에 등장한 모든 숫자들과 부분수열로 묶일 수 있다. 이중 최선은 최대 길이 2가 기록되어 있는 두 번째 값에 1(자기 자신의 길이)을 더하는 것이다. 이때 최대 길이의 바이토닉 수열은 1,2,4이다.
내려가는 상태의 경우에도, 위와 유사한 과정으로 최대 길이 1을 저장한다.
위와 같은 과정을 반복해 수열의 마지막 숫자까지 처리하면 결과는 다음과 같다. 발견할 수 있었던 가장 큰 길이의 바이토닉 수열의 길이는 아래 표에 저장된 값 중 최대인 5가 된다.
| 수열 | 1 | 2 | 1 | 4 | 5 | 1 |
|---|---|---|---|---|---|---|
| 올라가는 상태에서의 최대 길이 | 1 | 2 | 1 | 3 | 4 | 1 |
| 내려가는 상태에서의 최대 길이 | 1 | 1 | 3 | 1 | 1 | 5 |
위 과정을 정리하면 다음과 같다.
- 수열의 숫자를 올라가는 상태에 있다고 가정했을 때, 그리고 내려가는 상태에 있다고 가정했을 때 현재까지의 최대 바이토닉 수열의 길이를 저장한다.
- 이미 저장해 두었던 최대 바이토닉 수열의 길이를 참고하여, 그 수열과 이어나갈 수 있는 경우 그 길이에 1(자기 자신의 길이)을 더한다.
- 올라가는 상태에서는 바이토닉 수열의 마지막 숫자보다 현재 처리 중인 수열의 숫자가 더 커야 하며, 내려가는 상태에서는 바이토닉 수열의 마지막 숫자보다 현재 처리 중인 수열의 숫자가 더 작아야 한다.
- 바이토닉 수열의 올라가는 방향을 내려가는 방향으로 전환시킨다고 가정할 때와, 전환시키지 않는다고 가정할 때를 모두 고려한다.
이 로직을 코드로 다시 한번 살펴보자.
for (int i = 0; i < n; i++) {
// 만약 자기 자신을 바이토닉 수열의 시작점으로 간주한다면, 바이토닉 수열의 길이는 1이다.
upwardMemo[i] = 1;
downwardMemo[i] = 1;
// 바이토닉 수열의 방향이 전환된다고 가정할 때, 올라가는 상태의 바이토닉 수열의 길이 중 가장 큰 것을 찾기 위해 사용된다.
int peek = 0;
for (int j = 0; j < i; j++) {
if (numbers[j] < numbers[i]) {
// 올라가는 상태의 수열과 자기 자신을 이음
upwardMemo[i] = Math.max(upwardMemo[i], upwardMemo[j] + 1);
}
else if (numbers[j] > numbers[i]) {
// 내려가는 상태의 수열과 자기 자신을 이음
downwardMemo[i] = Math.max(downwardMemo[i], downwardMemo[j] + 1);
peek = Math.max(peek, upwardMemo[j]);
}
}
// 방향을 전환해 내려가는 상태로 만들었을 때 더 이득이라면 그 길이 값을 사용
downwardMemo[i] = Math.max(downwardMemo[i], peek + 1);
}
참고로, 백준 사이트에 예제로 제시된 테스트케이스의 경우 아래와 같이 기록된다.
| 수열 | 1 | 5 | 2 | 1 | 4 | 3 | 4 | 5 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|
| 올라가는 상태에서의 최대 길이 | 1 | 2 | 2 | 1 | 3 | 3 | 4 | 5 | 2 | 1 |
| 내려가는 상태에서의 최대 길이 | 1 | 1 | 3 | 4 | 3 | 4 | 3 | 1 | 6 | 7 |
