백준 11053

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

처음 풀때 잘 못 생각했었다 순열안에 수를 뽑아 증가하는 수열을 만드는 거라 생각해서

처음 부터 다시 풀어야 했다

이번 꺼는 생각하는 게 좀 어려웠다 자기 자신의 이전의 경로의 수가 dp로 들어가야한다.

10 20 10 30 20 50

이렇게 수열이 있으면 처음 이렇게 만 있을 때 증가하는 수열들은 각각 하나 씩이라고 생각하자

그 후에 내 이전의 원소들을 보면서 비교한다 내 이전의 원소가 나보다 작으면

나의 수에 내 이전 원소 까지의 증가수를 합쳐준다 

예시로 

20이 10을 만나게 되면 10은 하나짜리 증가 수열이고 20은 10보다 크니

10 20은 증가수열이다 이에 서로까지의 증가 수열 수를 더해준다 이에 20은 

2의 증가 수열을 갖는다

하지만 이 때 내 이전 원소가 나보다 작을 수 있는 경우의 수가 여러 개이므로 

내 이전까지의 증가수열 수 + 1 끼리를 비교하여 가장 큰값을 내가 갖고 있어야 한다

이에 dp[i]=max(dp[i],dp[j]+1)  이 필요하다

이에 자기자신의 값과 내 이전의 증가수열이 나를 만났을 때의 개수 와 비교해 준다

이렇게 점점 자기자신보다 작은애까지의 증가수열 + 나의 값이 최대가 되는 것을 구하는게

핵심이다

#include <iostream>
using namespace std;
int max(int x, int y)
{
	return x > y ? x : y;
}
int main() {
	int arr[1001];
	int dp[1001]; //자신 까지의 증가 수열 수
	int maxnum=0;
	int inputn;
	cin >> inputn;
	for (int i = 0; i < inputn; i++) {
		cin >> arr[i];
		dp[i] = 1;
	}

	for (int i = 1; i < inputn; i++) {
		for (int j = 0; j <= i; j++) {
			if (arr[i] > arr[j]) {
				dp[i] = max(dp[i], dp[j]+1);
			}
		}
	}
	
	for (int i = 0; i < inputn; i++) {
		if (dp[i] > maxnum)
			maxnum = dp[i];
	}

	cout << maxnum;
}