백준 문제풀이
[백준][dp] 11054 가장 긴 바이토닉 부분 수열 c++ 구현
꽁이꽁설꽁돌
2024. 10. 6. 16:47
728x90
반응형
목차
https://www.acmicpc.net/problem/11054
문제
참고
https://be-senior-developer.tistory.com/23
[백준][dp] 11053 가장 긴 증가하는 부분 수열 c++ 구현
목차 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50
be-senior-developer.tistory.com
위의 문제를 풀어보면 쉽게 접근할 수 있다.
문제 구현 방향
시작점에서 증가하는 가장 긴 수열과 끝점에서 증가하는 가장 긴 수열을 구해놓고 접근했다.(전 처리)
그 이후 이중 for문으로 둘을 합쳐 가장 큰 값을 구했다. (1000*1000이라 시간초과는 나지 않는다.)
합칠때 둘의 값 크기를 비교하는 것만 주의해주면 된다.
코드 구현
#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>
#include<stack>
using namespace std;
int N;
int arr[10001] = { 0 };
//시작점 dp
int upDp[10001];
//끝점 dp
int upDpE[10001];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
upDp[i] = 1;
upDpE[i] = 1;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
upDp[i] = max(upDp[i], upDp[j] + 1);
}
}
}
for (int i = N-1; i >=0; i--) {
for (int j = N-1; j > i; j--) {
if (arr[i] > arr[j]) {
upDpE[i] = max(upDpE[i], upDpE[j] + 1);
}
}
}
int m = 1;
//합쳐서 가장 큰 것을 구해준다.
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
//주의해야 할 부분
if(arr[i] > arr[j])
m = max(m, upDp[i] + upDpE[j]);
}
}
cout << m;
return 0;
}
반응형