[BOJ] 11722번 가장 긴 감소하는 부분 수열 c++
https://www.acmicpc.net/problem/11722
문제
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.
입력 1
6
10 30 10 20 20 10
출력 1
3
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 1001
int main() {
int N, maxval;
int num[MAX] = {0,};
int dp[MAX] = {0,};
int sorted[MAX] = {0,};
scanf("%d", &N);
for(int i = 1; i <= N; i++)
scanf("%d", &num[i]);
maxval = *max_element(num + 1, num + MAX);
for(int i = 1; i <= N; i++) {
dp[i] = *max_element(sorted + num[i] + 1, sorted + maxval + 1) + 1;
sorted[num[i]] = dp[i];
}
printf("%d\n", *max_element(dp + 1, dp + MAX));
}
11053번 가장 긴 증가하는 부분 수열에서 조금만 바꾸면 됐다. 이전에는 dp[i]에 *max_element(sorted + 1, sorted + num[i])
였던 부분에서 범위를 sorted + num[i] + 1, num의 가장 큰 원소 + 1
로 바꿨다. 그러니까 0 ~ 현재 숫자를 현재 숫자 + 1 ~ 가장 큰 숫자로 바꾼 것이 되겠다.
Author And Source
이 문제에 관하여([BOJ] 11722번 가장 긴 감소하는 부분 수열 c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@chowisely/BOJ-11722저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)