백준 11054번
오늘 풀어본 문제는 백준의 11054번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
수열 $S$ 가 어떤 수 $S_k$ 를 기준으로 $S_1 < S_2 < … S_{k-1} < S_k > S_{k+1} > … S_{N-1} > S_N$ 을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.
예를 들어, ${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$ 를 이루고 있는 $A_i$ 가 주어진다. $(1 ≤ N ≤ 1,000, 1 ≤ A_i ≤ 1,000)$
출력
첫째 줄에 수열 $A$ 의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.
풀이과정
1번째 시도
이 문제는 예전에 풀었던 가장 긴 증가하는 부분 수열과 비슷한 방법으로 풀 수 있다. 전체 수열에서 각 원소를 마지막 원소로 하는 ‘정방향’ 최장 증가 부분 수열과 ‘역방향’ 최장 증가 부분 수열의 각각의 길이를 합하면 해당 원소를 중심으로 한 부분 바이토닉 수열의 길이를 얻어낼 수 있다. 이 때 해당 바이토닉 수열에 중심 원소가 정확히 한 번 포함되어야 하기 때문에 1을 빼주면 된다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, maximum = 0;
cin >> N;
vector<int> A(N);
vector<int> increasing(N, 1);
vector<int> reverseIncreasing(N, 1);
for (int i = 0; i < N; i++) {
cin >> A[i];
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < i; j++) {
if (A[j] < A[i]) {
increasing[i] = max(increasing[i], increasing[j] + 1);
}
}
}
for (int i = N - 2; i >= 0; i--) {
for (int j = N - 1; j > i; j--) {
if (A[j] < A[i]) {
reverseIncreasing[i] = max(reverseIncreasing[i], reverseIncreasing[j] + 1);
}
}
}
for (int i = 0; i < N; i++) {
cout << increasing[i] << " ";
}
cout << "\n";
for (int i = 0; i < N; i++) {
cout << reverseIncreasing[i] << " ";
}
cout << "\n";
for (int i = 0; i < N; i++) {
maximum = max(maximum, increasing[i] + reverseIncreasing[i]);
}
cout << maximum - 1;
return 0;
}
실행 결과 ‘출력 초과’ 가 발생하였다.
2번째 시도
부분 수열의 길이가 제대로 저장되는 지 확인하기 위해 넣었던 코드를 삭제하는 것을 깜빡했다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, maximum = 0;
cin >> N;
vector<int> A(N);
vector<int> increasing(N, 1);
vector<int> reverseIncreasing(N, 1);
for (int i = 0; i < N; i++) {
cin >> A[i];
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < i; j++) {
if (A[j] < A[i]) {
increasing[i] = max(increasing[i], increasing[j] + 1);
}
}
}
for (int i = N - 2; i >= 0; i--) {
for (int j = N - 1; j > i; j--) {
if (A[j] < A[i]) {
reverseIncreasing[i] = max(reverseIncreasing[i], reverseIncreasing[j] + 1);
}
}
}
for (int i = 0; i < N; i++) {
maximum = max(maximum, increasing[i] + reverseIncreasing[i]);
}
cout << maximum - 1;
return 0;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
확실히 예전에 비해서 어떤 문제를 보고 적절한 풀이법을 생각해내는 능력이 성장한 것 같다. 예를 들어 오늘 풀었던 문제의 제약조건을 보고 요소의 개수가 1000개를 넘지 않는다는 점을 이용하여 $O(N^2)$ 의 시간 복잡도를 이용해도 괜찮다는 것을 간파하고 간단하게 구현하여 빠르게 문제를 해결할 수 있었다.
CLASS 3 문제도 조금 어려워 하며 풀었던 예전에 비교하면 실력이 꽤 늘었다는 것이 느껴진다. 물론 이 수준 너머의 무시무시한 세계가 존재한다는 걸 알고 있기 때문에 수련을 게을리 하지는 않을 것이다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/11054