백준 - 11568번 민준이의 계략

문제

숫자들이 주어질 때, 가장 긴 증가하는 순열의 길이 알아내기

생각

DP로 증가하는 부분 순열 만들어서 가장 긴 순열 길이 알아낸다!!

흐음 예전에 답보고 풀었는데도, 다시 생각하니까 몰랐다 ㄹㅈㄷ

'index 번째 수를 포함해서 최대 value 길이만큼 부분 수열을 만들 수 있음' 을 알아야하는건
어렴풋이 기억에 남았지만, 이중 포문 도는 건 까먹었따

vector<int> maxCardNum;
//자기 자신을 포함한 만들 수 있는 최대 증가 부분 순열의 길이

for (int i = 1; i < n; i++) {
    maxCardNum.push_back(1); //자기 혼자 일 때 최소 1
    for (int j = 0; j < i; j++) {
        if (num[j] < num[i]) {
        // 그 전에 만들어진 부분 순열이 있고, 그 부분 순열의 마지막 애보다 크면
        // 자기 자신도 껴서 새 부분 순열 만들기 가능
            maxCardNum[i] = max(maxCardNum[i], maxCardNum[j] + 1);
        }
    }
    result = max(result, maxCardNum[i]);
    //어느 수를 마지막으로 부분 순열 만든게 최대인 지 모르니까
    //돌 때 마다 최대 길이 저장
}

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

int n;

int num[1005];
vector<int> maxCardNum;

int findMaxCount() {
	maxCardNum.push_back(1);
	int result = maxCardNum[0];

	for (int i = 1; i < n; i++) {
		maxCardNum.push_back(1);
		for (int j = 0; j < i; j++) {
			if (num[j] < num[i]) {
				maxCardNum[i] = max(maxCardNum[i], maxCardNum[j] + 1);
			}
		}
		result = max(result, maxCardNum[i]);
	}

	return result;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}

	cout << findMaxCount();

	return 0;
}