백준 10571 다이아몬드 C++

문제

어떠한 다이아몬드의 가치는 그 다이아몬드의 중량인 캐럿과 선명도에 의해서 결정됩니다. 즉, 작지만 선명한 다이아몬드가 크고 선명하지 않은 다이아몬드보다는 가치가 높습니다. 다이아몬드의 선명도는 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

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

---

입력

테스트 케이스의 개수 T가 주어지고 (1≤T≤100) 각 테스트 케이스마다 다이아몬드의 정보의 개수 N (1≤N≤200)이 주어집니다. 그리고 N개의 줄에 걸쳐서 다이아몬드의 무게와 선명도 wi, ci가 주어집니다 (0≤wi,ci≤100).

---

출력

각 테스트 케이스마다 다이아몬드의 가치가 높아지는 부분열중 최장의 것의 길이를 구하세요.

---

N개의 다이아몬드가 있고, 다이아몬드는 각각 무게와 선명도가 존재합니다.

이떄 다이아몬드의 가치는, 중량이 높아지고, 선명도 값이 낮아지는 것입니다. 다이아몬드의 가치가 높아지는

부분 열 중, 최장의 것을 구해야 합니다.

N의 크기가 최대 200이므로, O(N^2)의 풀이를 생각해서 작성하였습니다.

---

#include <iostream>
using namespace std;

struct diamond{
    double w;
    double c;
};

typedef struct diamond dia;

int max(int a,int b){
    if(a>b){
        return a;
    }
    else{
        return b;
    }
}

int main(void){
    int t;
    cin >> t;
    while(t--){
        
        int n;
        cin >> n;
        
        int max_length = -1;
        dia arr[201];
        int dp[201];
        for(int i = 0;i<n;i++){
            cin >> arr[i].w >> arr[i].c;
        }
        
        //최소 길이 1로 초기화
        for(int i = 0;i<n;i++){
            dp[i] = 1;
            
            for(int j = 0;j<i;j++){
                //무게가 더 크고, 선명도가 더 작아야 함
                if(arr[i].w > arr[j].w && arr[i].c < arr[j].c){
                    if(dp[i] < dp[j] + 1){
                        dp[i] = dp[j] + 1; 
                    }
                }
            }
            max_length = max(max_length,dp[i]);
        }
        
        printf("%d \n",max_length);
        
    }
}