[BAEKJOON] 2352 반도체 설계

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; scanf("%d", &n); vector<int>map(40001), DP(40001, 0); for (int j = 0; j < n; j++) scanf("%d", &map[j]); int Max = 0; for (int j = 0; j < n; j++) { Max = 0; for (int k = 0; k < j; k++) { if (map[k] < map[j]) Max = max(Max, DP[k]); } DP[j] = Max + 1; } Max = 0; for (int j = 0; j < n; j++) Max = max(Max, DP[j]); printf("%d", Max); return 0; }

LIS...

증가하는 가장 큰 부분 수열..이다..ㅠㅠㅠ

아..왜 이생각을 못했을까...

결국 겹치지 않으려면 들어오는 수가 차례대로 증가해야한다

그것이 가장 큰 수이다.

어짜피 왼쪽은 순서대로이기 때문이다

ㅠㅠㅠㅠ아..ㅠㅠㅠㅠㅠ너무 아쉽다

다음부터는 이런 문제를 꼭 풀도록! 창의적으로 생각해야겠다!