득이공간
[백준 C++] 11053 가장 긴 증가하는 부분 수열 - 다이나믹프로그래밍 본문
#include <iostream>
using namespace std;
int Sequence[1000];
int Length[1000];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int MaxLength = 0;
int N;
cin >> N;
for (int i = 0; i < N; ++i)
{
cin >> Sequence[i];
for (int j = 0; j < i; ++j)
{
if (Sequence[j] < Sequence[i]
&& Length[j] > Length[i])
{
Length[i] = Length[j];
}
}
Length[i] += 1;
if (Length[i] > MaxLength)
{
MaxLength = Length[i];
}
}
cout << MaxLength;
}
수열의 처음 원소부터 마지막 원소까지 DP 배열을 채워주면서 푸는 문제입니다.
모든 원소를 순차 탐색하면서 현재 원소 이전 원소 중에 현재 원소보다 값이 작은 원소가 존재하면
해당 원소의 DP 값과 현재 원소의 DP 값을 비교해서 더 큰 값을 넣어주고 +1을 해줍니다.
DP 배열을 모두 채우고 나면 최대값을 출력합니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 16953 A → B - 너비우선탐색 (0) | 2024.02.20 |
---|---|
[백준 C++] 11725 트리의 부모 찾기 - 너비우선탐색 (0) | 2024.02.20 |
[백준 C++] 15654 N과 M (5) - 백트래킹 (0) | 2024.02.20 |
[백준 C++] 15650 N과 M (2) - 백트래킹 (1) | 2024.02.20 |
[백준 C++] 16928 뱀과 사다리 게임 - 너비 우선 탐색 (0) | 2024.02.19 |