이 문제는 dp알고리즘 중에서도 LIS( Longest Increasing Subsequence) 입니다.
최대 부분 증가 수열이라고도 합니다.
만약
10 20 40 30 70 50 60 의 배열이 있을때
10 20 30 50 60 이 최대 부분 증가 수열로써 가장 길이가 깁니다.
아래와 같은 뉘앙스로 해결해주면 됩니다.
#include <iostream>
using namespace std;
struct info {
int count;
int port_num;
};
int n,result=0;
struct info dp[40001];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> dp[i].port_num;
dp[1].count = 1; //초기값 설정
for (int i = 2; i <= n; i++) {
for (int j = i - 1; j > 0; j--) {
if (dp[i].port_num > dp[j].port_num &&dp[i].count < dp[j].count)
dp[i].count = dp[j].count;
}
dp[i].count++;
if (result < dp[i].count)
result = dp[i].count;
}
cout << result << endl;
}
하지만 문제가 생깁니다. 위의 알고리즘은 O(n^2)을 가지게 됩니다.
이 문제에서는 n(1 ≤ n ≤ 40,000) 입니다. 즉, 최악의 경우에 O(n^2) = 40000 X 40000 = 1,600,000,000 이 되기 때문에 시간제한 2초로는 어림도 없죠 ( 1억번 연산 당 대략 1초)
즉 O(n) or O(nlgn)의 풀이법을 찾아야합니다. 해당 문제에서 이전값들을 비교해서 결과를 도출해야 하기 때문에 O(n)은 불가능합니다.
C++ stl에서 제공하는 기능은 1.Lower Bound 2.인덱스 트리 입니다. (정확한 메소드내용은 모르겠지만 탐색시 O(lgn)번의 탐색으로 위치를 전달합니다.
#include <iostream>
#include <algorithm>
using namespace std;
int n = 0,len=1;
int arr[40001] ;
int arr2[40001] = { 0 };
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
arr2[len] = arr[1]; //초기값 설정
for (int i = 2; i <= n; i++) {
if (arr2[len] < arr[i]) {
arr2[++len] = arr[i];
}
else {
int val = lower_bound(arr2 + 1, arr2 + len + 1, arr[i]) - arr2;
arr2[val] = arr[i];
}
}
cout << len << endl;
}
생각해보니 arr는 필요가 없더군요 매번 값을 입력받고 arr2에 저장해주면 됩니다.
그리고 lower_bound메소드의 역할을 이분탐색을 통해서 구현을 할 수 도 있겠군요.
#include <stdio.h>
#define M 40010
int port[M];
int up[M] = { 0x80000001, };
int ref[M];
int n, max;
int search(int left, int right, int x) {
int mid;
if (left > right) return left;
mid = (left + right) / 2;
if (ref[mid] < x)
return search(mid + 1, right, x);
else if (ref[mid] > x)
return search(left, mid - 1, x);
else
return mid;
}
int main() {
int i, cursor;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%d", port + i);
cursor = search(0, max, port[i]);
ref[cursor] = port[i];
up[i] = cursor;
if (cursor > max)
max = cursor;
}
printf("%d\n", max);
return 0;
}
#include <iostream>
using namespace std;
int t = 0, a = 0, b = 0, result = 0;
void festival1(int num) {
if (num == 1)
result += 5000000;
else if (num <= 3)
result += 3000000;
else if (num <= 6)
result += 2000000;
else if (num <= 10)
result += 500000;
else if (num <= 15)
result += 300000;
else if (num <= 21)
result += 100000;
}
void festival2(int num) {
if (num == 1)
result += 5120000;
else if (num <= 3)
result += 2560000;
else if (num <= 7)
result += 1280000;
else if (num <= 15)
result += 640000;
else if (num <= 31)
result += 320000;
}
int main() {
cin >> t;
while (t--) {
result = 0;
cin >> a >> b;
if (a != 0)
festival1(a);
if (b != 0)
festival2(b);
cout << result << endl;
}
}
