백준 c++ 11053 "가장 긴 증가하는 부분 수열" -PlusUltraCode-

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;
}