[C/C++] 백준 - 10571번 : 다이아몬드

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

10571번: 다이아몬드

문제

어떠한 다이아몬드의 가치는 그 다이아몬드의 중량인 캐럿과 선명도에 의해서 결정됩니다. 즉, 작지만 선명한 다이아몬드가 크고 선명하지 않은 다이아몬드보다는 가치가 높습니다. 다이아몬드의 선명도는 0.0-10.0의 스캐일로 표현할 수 있는데, 0.0의 선명도는 완벽하게 선명한 다이아몬드를 나타내고 10.0은 가장 결함이 많은 다이아몬드를 나타냅니다.

N개의 다이아몬드의 중량 wi와 선명도 ci의 정보가 주어졌을때, 이 중에서 다이아몬드의 중량이 높아지고, 선명도 값이 낮아지는 부분열 중 최장의 것의 길이를 구하세요. 예를들어 주어진 정보가 다음과 같다면

wi	ci
1.5	9.0
2.0	2.0
2.5	6.0
3.0	5.0
4.0	2.0
10.0	5.5

다이아몬드 중량이 높아지고, 선명도 값이 낮아지는 부분열 중 길이가 최장인 것은 다음과 같습니다.

1.5	9.0
2.5	6.0
3.0	5.0
4.0	2.0

왜냐하면 표에 나와있는 부분열을 보면, 무게는 증가하고, 선명도의 값은 감소하기 때문입니다.

 

---

 

문제 설명에도 있는것처럼 조건에 맞게 가장 긴 증가하는 부분 수열을 구하면 되는 알고리즘이다.

5초의 시간제한이기 때문에 lower_bound를 사용하지 않고 O(n^2)의 LIS알고리즘을 사용해도 충분히 통과할 수 있다.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <climits>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1234567
#define endl '\n'
#define pil pair<int,int>

using namespace std;

typedef struct information {
	double first;
	double second;
}Information;

int N;
Information ps[300 + 1];
int cache[300 + 1];

int solution() {
	memset(cache, -1, sizeof(cache));
	int answer = 1;
	for (int index = 1; index <= N; index++) {
		cache[index] = 1;
		for (int prev = 1; prev < index; prev++) {
			if ((ps[prev].first < ps[index].first && ps[prev].second > ps[index].second)) {
				cache[index] = max(cache[index], cache[prev] + 1);
				answer = max(answer, cache[index]);
			}
		}
	}
	return answer;
}

void input() {
	int testCase;
	cin >> testCase;
	for (int tc = 0; tc < testCase; ++tc) {
		cin >> N;
		for (int i = 1; i <= N; i++) {
			cin >> ps[i].first >> ps[i].second;
		}
		
		cout << solution() << endl;
	}
}

int main() {
	fastio;
	input();
	
	return 0;
}