Study hard
(c++)백준 11053번: 가장 긴 증가하는 부분 수열 본문
https://www.acmicpc.net/problem/11053
이번에도 dp배열을 뒤에서부터 쌓았다. (앞에서부터 쌓아도 된다.)
※점화식※
dp[i] : i를 수열의 첫번째 숫자로 했을 때 증가하는 수열의 최대 길이
dp[1~N] 1로 초기화
i=N-1부터 시작하여 1이 될때까지 진행하고,
2중 for문으로 j=i+1부터 N번째 값까지 i번째 값과 비교해서 i번째 값보다 크다면 dp[j] 저장,
큰 값이 여러개면 가장 큰 dp[j] 저장하여 안쪽 for문 나왔을 때 dp[i]에 더한다.
#include <iostream>
using namespace std;
int N;
int A[1001];
long long dp[1001];
void DP() {
long long Max = -1;
//모두 1로 초기화
for (int i = 1; i <= N; i++) {
dp[i] = 1;
}
for (int i = N - 1; i >= 1; i--) {
long long maxLength = 0;
for (int j = i + 1; j <= N; j++) {
//자신보다 더 큰 값 나타나면 그 값을 처음으로 했을 때
//가장 긴 부분 수열 길이를 더하기 (여러개면 부분 수열 길이가 가장 긴 것 더하기)
if (A[i] < A[j] && maxLength < dp[j]) {
maxLength = dp[j];
}
}
dp[i] += maxLength;
}
for (int i = 1; i <= N; i++) {
if (Max < dp[i])
Max = dp[i];
}
cout << Max << endl;
}
int main() {
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> A[i];
}
DP();
return 0;
}
'백준 > DP' 카테고리의 다른 글
(c++)백준 11722번: 가장 긴 감소하는 부분 수열 (0) | 2020.06.09 |
---|---|
(c++)백준 11055번: 가장 큰 증가 부분 수열 (0) | 2020.06.09 |
(c++)백준 2156번: 포도주 시식 (0) | 2020.06.09 |
(c++)백준 9465번: 스티커 (0) | 2020.06.09 |
(c++)백준 2193번: 이친수 (0) | 2020.06.09 |