반응형

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 가장 긴 바이토닉 부분 수열 (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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.
[ 코드 ]
#include<iostream> #include<algorithm> #include<vector> using namespace std; vector <int> dp1(1001); // 가장 긴 증가하는 부분 수열 vector <int> dp2(1001); // 가장 긴 감소하는 부분 수열 int main() { int N; // 수열 A의 크기 cin >> N; vector <int> A(N);// 수열 A for (int i = 0; i < N; i++) { cin >> A[i]; } for (int n = 0; n < N; n++) // 증가하는 부분 수열 (i에서 끝남) { dp1[n] = 1; for (int i = 0; i < n; i++) { if (A[n]>A[i]) { dp1[n] = max(dp1[n], dp1[i] + 1); } } } for (int n = N-1; n >=0; n--) // 감소하는 부분 수열 (i에서 시작) { dp2[n] = 1; for (int i = n+1; i < N; i++) { if (A[n] > A[i]) { dp2[n] = max(dp2[n], dp2[i] + 1); } } } int result = 0; for (int i = 0; i < N; i++) { result = max(result, (dp1[i] + dp2[i] - 1)); } cout << result; return 0; }
반응형
'문과 코린이의, [C. C++] 기록 > C++ 백준 문제풀이' 카테고리의 다른 글
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 타일 채우기 (2133) (0) | 2021.07.27 |
---|---|
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 연속합 2 (13398) (0) | 2021.07.26 |
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 가장 긴 감소하는 부분 수열 (11722) (0) | 2021.07.26 |
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 가장 큰 증가 부분 수열 (11055) (0) | 2021.07.26 |
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 정수 삼각형 (1932) (0) | 2021.07.26 |