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

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

 

문제를 풀기 위해서는 증가하는 부분 수열과, 감소하는 부분 수열을 각각 계산하여 합하는 것이 가장 간단해 보였다.

 

 

---

 

문제의 입력값을 위와 같이 표현할 것이다.

그림의 표는 순서대로 입력된 값들을 의미하며 표 위의 막대들은 해당 값을 가시성 좋게 높이로 표현한 것이다.

 

또한, 문제에서 명시된 바이토닉 부분 수열의 정의는 아래와 같다.

 

즉 어떤 수 k를 기준으로 좌우 방향으로 순감소 수열이라면 그 전체를 바이토닉 수열이라고 부른다는 것이다.

우리는 임의의 수열이 있을 때, 그중 일부만을 취하여 (=부분 수열) 바이토닉 수열을 만들 수 있다.

 

아래의 두 예시처럼 일부만을 취하여 바이토닉 수열을 만들면 그것이 바이토닉 부분 수열이다.

 

1,2,1 의 바이토닉 부분 수열 예시

1, 4, 5, 2, 1 의 바이토닉 부분 수열 예시

 

물론 위의 예시들이 가장 긴 바이토닉 부분 수열은 아니다.

간단한 규칙을 이용하여 문제의 답을 구해보자.

---

규칙은 아래와 같다.

 

• (규칙 A) 좌측에서 시작하여 임의의 k 번째 수 까지, 순증가 수열의 최댓값을 구한다.
  • (규칙 A-1) 좌측에서 시작하여 자기 자신보다 먼저 등장한 인덱스 중 자신보다 작은 수를 찾는다.
  • (규칙 A-2) 규칙 A-1에 해당하는 수들 중 순증가 수열의 최댓값을 구한다.
  • (규칙 A-3) 규칙 A-2에 의해 얻어진 최댓값에 1을 더하여 자기 자신의 값으로 저장한다.
• (규칙 B) 우측에서 시작하여 임의의 k 번째 수 까지, 순증가 수열의 최댓값을 구한다.
  • 규칙 A와 동일하며 방향만 다르다.
• (규칙 C) 규칙 A와 규칙 B에서 얻어낸 k번째 수의 최댓값 2개를 더하여 k번째 수를 바이토닉 수열의 중심으로 하였을 때의 바이토닉 부분 수열 길이를 계산한다.
  • (규칙 C-1) 전체 수열에 대하여 가장 긴 바이토닉 부분 수열의 길이를 얻어낸다.

 

 

규칙을 따라 단계별로 수행해보자.

 

(규칙 A)에 의해 좌측에서 탐색을 시작한다.

(규칙 A-1)에 의해 자기 자신보다 먼저 나온 값들을 확인해야 하지만, 가장 첫 인덱스이므로 찾을 수 없다.

(규칙 A-2)에 의해 최댓값을 구해야 하지만 첫 인덱스이므로 값이 없다 (= 최댓값이 0이다)

 

 

(규칙 A-3)에 의해 0 + 1 이 저장된다.

 

 

계속하여 탐색을 진행한다.

 

(규칙 A-1)에 해당하는 값이 존재한다.

(규칙 A-2)에 의해 최댓값인 1이 탐색되며, (규칙 A-3)에 의해 1+1 인 2가 저장된다.

 

 

계속하여 탐색을 진행하고, 앞선 인덱스 중에 2보다 작은 값은 1 밖에 없으므로 1+1인 2가 저장된다.

 

 

 

이러한 방식으로 계속하여 탐색을 진행하게 된다.

 

 

 

 

 

탐색을 진행하다 보면 다음과 같은 상황이 발생한다.

 

 

(규칙 A-1)에 의해 탐색된 값이 1, 2, 1로 3개가 되었다.

이경우에는 (규칙 A-2)에 의해 순증가 수열의 크기가 최대인 값에 1을 더 해주면 된다.

 

 

 

 

 

 

 

 

이러한 방식으로 탐색을 계속 진행하면 (규칙 A)가 종료된다.

 

 

 

 

 

(규칙 B)는 A와 방향만 반대인 동일한 동작이다. 간단히 구현할 수 있다.

 

 

 

 

 

 

(규칙 A)와 (규칙 B)가 종료되면 (규칙 C)를 적용할 수 있다.

 

 

 

 

(규칙 C)를 적용하면 다음과 같은 값을 얻을 수 있다. 위의 두 수열을 세로로 합해줬을 뿐이다.

 

 

 

 

(규칙 C-1)에 의해 최댓값인 8을 얻어 낼 수 있다.

 

 

 

 

이때 주의할 점은 8을 그대로 제출하면 안 된다는 점인데, 이유는 최댓값의 인덱스는 좌측 수열에도 포함되고, 우측 수열에도 포함되었기 때문에 2번 카운팅 되기 때문이다.

 

 

즉 중복 카운팅 된 1을 감하여 출력해야 정답을 얻을 수 있다.

 

---

 

code

GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지