티스토리 뷰
728x90
https://www.acmicpc.net/problem/11054
11054번: 가장 긴 바이토닉 부분 수열
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
www.acmicpc.net
동적계획법 C++
가장 긴 바이토닉 부분 수열 문제
접근 방법
가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열이 중첩된 문제
0부터 i 까지의 가장 긴 증가하는 부분 수열을 구하고, i 부터 n까지 감소하는 부분 수열을 구하여 합한 값으로 구한다.
증가하는 부분 수열은 차이가 없지만, 감소하는 부분 수열은 원래는 i까지 감소하는 부분수열을 구했었는데
여기선 i부터 n까지 감소하는 부분 수열을 구한다는 점이 다르다.
소스코드
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n ;
int num[n];
int lengthasc[n];
int lengthdesc[n];
int result = 0;
for(int i = 0 ; i < n ; i++){
cin >> num[i];
}
for(int i = 0 ; i < n ; i++){
lengthasc[i] = 1;
for(int j = 0 ; j < i ; j++){
if(num[j] < num[i] && lengthasc[j] >= lengthasc[i]){
lengthasc[i] = lengthasc[j]+1;
}
}
}
for(int j = n-1 ; j >= 0 ; j--){
lengthdesc[j] = 1;
for(int k = j+1 ; k < n ; k++){
if(num[j] > num[k] && lengthdesc[j] <= lengthdesc[k]){
lengthdesc[j] = lengthdesc[k]+1;
}
}
}
for(int i = 0 ; i < n ; i++){
if(result < lengthdesc[i]+lengthasc[i]-1)
result = lengthdesc[i]+lengthasc[i]-1;
}
cout << result;
return 0;
}
728x90
'알고리즘 문제풀이' 카테고리의 다른 글
[백준 12865] 알고리즘 53일차 : 평범한 배낭 (C++, Swift) (0) | 2020.08.28 |
---|---|
[백준 11057] 알고리즘 52일차 : 오르막 수 (0) | 2020.08.27 |
[백준 9095] 알고리즘 50일차 : 1,2,3더하기 (0) | 2020.08.25 |
[백준 1920] 알고리즘 49일차 : 수 찾기 (0) | 2020.08.24 |
[백준 11722] 알고리즘 48일차 : 가장 긴 감소하는 부분 수열 (0) | 2020.08.21 |
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 웹크롤링
- 스택
- 그리디알고리즘
- 수학
- 파이썬
- 트리
- dp
- 동적계획법
- 백트래킹
- dfs
- 문자열
- 게임이론
- BFS
- 알고리즘
- 토마토
- 브루트포스
- 이분탐색
- 최대힙
- Swift
- 투포인터
- 자바
- Stack
- 프로그래머스
- 우선순위큐
- 최소힙
- 다이나믹프로그래밍
- 최단경로
- 백준
- c++
- 정렬
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
글 보관함