백준 [11053] "가장 긴 증가하는 부분 수열"

가장 긴 증가하는 부분 수열은 DP를 이용해 해결하는 문제였다. 하지만 문제를 정확히 이해하지 못하고 예제 입력1만을 보고 잘못된 풀이를 생각하게 되었다. 배열을 정렬하고 중복된 값을 제거한 길이를 출력으로 설정했는데 오답이였다.

#include <iostream>
#include <deque>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 10001

using namespace std;

int n;
vector<int> a;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	
	a.resize(n);

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

	sort(a.begin(), a.end());
	a.erase(unique(a.begin(), a.end()), a.end());

	cout << a.size();

	return 0;
}

input으로 횟수 n과 수열 a를 입력 받는다.
vector.emplace_back(k)를 통해 수열중 중복으로 들어있지 않은 수만을 입력 받는다.
현재 입력받은 x와 a수열 내 y들을 전부 비교해 만약 현재 입력받은 x가 크고 각 수열의 길이dp[j]보다 dp_max(0)가 작은 상황은 아직 수열의 길이가 늘어나지 않은 상황이기에 dp_max에 dp[j]에 해당하는 수열의 길이를 넣어준다.

그리고 dp[i]가 만약 수열내 y보다 컸다면 dp[j]길이를 이어받아 +1이 되고 아니라면 현재 입력받은 x만이 수열의 길이에 영향을 주기에 dp[i] = 1이 된다 (dp_max+1)
그리고 수열의 길이중 최대길이 수열을 구해야 하기에 매번 max함수를 통해 최대 길이 수열을 업데이트 해주고 마지막에 출력해준다.

#include <iostream>
#include <deque>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 10001

using namespace std;

int n, k;
vector<int> a;
vector<int> dp;
int answer = 0;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    int T;
    int N, M, K, H;
    int X, Y;
    int answer = 0;

    int dp[1001];
    cin >> T;

    for (int i = 0; i < T; i++) {
        cin >> K;
        a.emplace_back(K);
        int dp_max = 0;

        for (int j = 0; j < a.size(); j++) {
            if (a[i] > a[j]) {
                if (dp_max < dp[j])
                    dp_max = dp[j];
            }
        }
        dp[i] = dp_max + 1;
        answer = max(answer, dp[i]);
    }

    cout << answer << endl;

    return 0;
}