백준/동적프로그래밍
백준 c++ 11053 "가장 긴 증가하는 부분 수열" -PlusUltraCode-
PlusUltraCode
2024. 5. 1. 17:47
https://www.acmicpc.net/problem/11053
[필자 사고]
처음 문제를 보고 있을 때는 완전탐색으로 문제를 풀어 나갔다. 다만 문제가 틀리고
채점 계시판에 있는 반례를 본 후 완전탐색이 아닌 Dp로 풀기로 방향을 바꿨다.
기존 알고 있던 dp는 처음부터 차례대로 증가하는 형태로 쌓아가는 느낌이 많았다.
이 문제는 증가는 하지만 index가 작은 값들을 수시로 검사하는 형태로 쌓아가는 방식이다.
dp[i] = max(dp[i], dp[k]+1) 단 i>k
이 사고만 할 수 있으면 문제를 쉽게 풀 수 있다.
다른 후기들을 찾아보니 이 문제는 LIS의 기본 문제라한다. 기본 개념이 들어간 문제이니 기억해야 겠다.
[소스 코드]
#include<iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
vector<int> Arr;
vector<int> Dp;
int N;
int Result = 1;
void Input() {
cin >> N;
for (int i = 0; i < N; i++) {
int num;
cin >> num;
Arr.push_back(num);
}
}
void Solve() {
Dp.resize(N,1);
for (int i = 1; i < N; i++) {
for (int k = i - 1; k >= 0; k--) {
if (Arr[i] > Arr[k]) {
Dp[i] = max(Dp[i], Dp[k] + 1);
}
}
Result = max(Dp[i], Result);
}
}
int main(void) {
Input();
Solve();
cout << Result;
}